如何生成一定大小的集合分区？ [英] How do I generate set partitions of a certain size?

问题描述

我想以一种特定的方式为一个集合生成分区：我需要在生成这些分区的过程中过滤掉所有大小不为N的分区。通用解决方案是 生成所有唯一子集

I would like to generate partitions for a set in a specific way: I need to filter out all partitions which are not of size N in the process of generating these partitions. The general solution is "Generate all "unique" subsets of a set (not a powerset)".

对于具有以下子集的集合 S ：

For the set S with the following subsets:

[a,b,c]
[a,b]
[c]
[d,e,f]
[d,f]
[e]

和以下唯一元素：

a, b, c, d, e, f

以参数 N = 2 应为：

[[a,b,c], [d,e,f]]

以下分区应通过函数/方法过滤掉：

While the following partitions should be filtered out by the function/method:

[[a,b,c], [d,f], [e]]
[[a,b], [c], [d,e,f]]
[[a,b], [c], [d,f], [e]]

底层数据结构并不重要，可以是数组，集合或其他任何东西。

The underlying data structure is not important and could be arrays, sets or whatever.

原因：我需要在拥有所有分区的完整集合之前过滤掉一些分区，因为生成所有分区的函数/方法在计算上是相当密集的。

Reason: I need to filter some partitions out before I have the full set of all partitions, because the function/method which generates all partitions is rather computationally intensive.

根据 生成集合的分区，可能的分区数量可能非常庞大：用于23个元素的44152005855084346。我的数据在起始集中是50-300个元素，因此在将它们保存到任何地方之前，我肯定需要过滤掉大小不等于N的分区。

According to "Generating the Partitions of a Set", the number of possible partitions can be huge: 44152005855084346 for 23 elements. My data is 50-300 elements in the starting set, so I definitely need to filter out partitions that have size not equal to N before I save them anywhere.

推荐答案

一旦您拥有了由Frederick Cheung链接的分区，请执行以下操作：

Once you have the partitions as given by Frederick Cheung that you linked, do:

partitions.select{|partition| partition.length == 2}

这篇关于如何生成一定大小的集合分区？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！