分区一套成k个块 [英] Partitioning a set into exactly k blocks
问题描述
我需要一个算法来生成一组的取值的所有分区成完全 K 的＆LT; | S |。的块
I have a need for an algorithm to generate all partitions of a set S into exactly k < |S| blocks.
注：我已经找到了算法生成所有可能的分区;我只需要在 K - 分区算法
Note: I have already found the algorithm for generating all possible partitions; I just need the k - partition algorithm.
你知道吗？
推荐答案
在我建议在深度为k-1串门通常的递归算法，铭记一个2级的递归方案，其中每个外递归步骤是评论停止建设的决定当前部分并开始建设的下一个部分，每个内部递归步骤是决定把一些元素到目前的一部分。这是一个相当不错的方案，因为这意味着在递归树的底部产生的个人K-分区，这样你就可以对他们立即在这一点上进行操作，如果你想，而不必把它们全部存储到一个巨大的数组随后进行处理（当然你仍然可以做，如果你想）。这里唯一的问题是要确保你不拉闸产生相同的分区中的超过方式 - 尤其是通过生成含有相同的部分两个分区，但顺序不同的部分。即，可避免通过强制对份进行排序。最简单的办法是随时添加的第一个（即最左边的）当你开始建立一个新的部分可用的元素 - 这保证了部件在一个分区都通过它们的元素最小位置进行排序
In the comments I suggested stopping "the usual recursive algorithm" at depth k-1, having in mind a 2-level recursion scheme where each outer recursion step was a decision to stop building the current part and start building the next part, and each inner recursion step was a decision to place some element into the current part. This is quite a nice scheme, since it means that the individual k-partitions are generated at the bottom of the recursion tree, so you can operate on them immediately at that point if you want, without having to store them all into a huge array for later processing (though of course you can still do that if you want). The only trick here is to make sure that you don't wind up generating the same partition in more than way -- in particular, by generating two partitions containing the same parts, but with those parts in a different order. That can be avoided by enforcing an ordering on parts. The simplest way is to always add the first (i.e. leftmost) available element whenever you start building a new part -- this guarantees that parts in a partition will be ordered by minimum position of their elements.
但是，如果你不介意的实例K-分区存储的完整列表，还有另一种方式，我认为是比较简单。下面应该足以帮你把一个简单的递归算法起来：
But if you don't mind instantiating the full list of k-partitions in memory, there's another way that I think is simpler. The following should be enough to help you put a simple recursive algorithm together:
考虑的S某个元素S在S.每k分区是完全两类：
Consider some element s in S. Every k-partition of S is in exactly one of two categories:
- 取值出现在相同的部分的一些其它元件。在这种情况下，从该部分删除s给出为S \ {S}的k分区。
- 取值出现在本身的一部分。在这种情况下，删除该整个部分给出为（k-1）为S \ {S} -partition。
在壳体（1）的所有分区可通过加入s到在为S \ {S}的k分区的部件之一来形成，并在壳体（2）的所有分区可以通过添加含有一个单独的部分来形成只发地与s \ {S}一（K-1）-partition。说服自己，这将产生的S所有的k-分区一次，只有一次。
All partitions in case (1) can be formed by adding s to one of the parts in a k-partition of S \ {s}, and all partitions in case (2) can be formed by adding a separate part containing only s to a (k-1)-partition of S \ {s}. Convince yourself that this will generate all k-partitions of S once and once only.
在递归，那么您需要考虑的唯一边界情况是当| S | ==的k - 在这种情况下，你需要返回单个分区组成的k个单套
During the recursion, the only boundary case you need to consider is when |S| == k -- in that case, you need to return the single partition consisting of k singleton sets.
这篇关于分区一套成k个块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
