生成集合的所有分区

Question

一组表格 A = {1, 2, 3, ..., n}。它被称为集合 A 的划分，一组 k<=n 元素遵循以下定理：

a) A 所有分区的并集是 A

b) A的2个分区的交集是空集（它们不能共享相同的元素）。

例如。 A = {1, 2,... n} 我们有分区：

{1, 2, 3}
{1, 2} {3}
{1, 3} {2}
{2, 3} {1}
{1} {2} {3}

这些理论概念在我的算法教科书中有介绍（顺便说一下，这一章是“回溯”一章的一部分）。我应该找到一种算法来生成给定集合的所有分区。我整天都在为这个问题苦苦挣扎，找不到解决方案。你能解释一下这个算法是如何工作的吗？另外，你能给我一个算法的伪代码草图吗？

Answer 1

如果你的集合不大（或者使用堆栈），你可以尝试递归答案：

原理如下，你有一个回馈函数:

rec_func(SET) = List of List of Set

并按如下方式工作：

rec_func(SET) =
  if SET = {empty}:
    // if no element, easy to give the answer
    return([[]])
  else:
    // 1. Remove one element from the set : 'a' to this set
    a = SET.pop()
    // 2. Call rec_func :
    list_of_list_of_set = rec_func(SET\'a')  
    response = []
    // 3. For every possibilities given by the function add the element 'a' :
    For every list_of_set in list_of_list_of_set  :
       // Case 1, you add 'a' to list_of_set
       response.push( [{'a'} + list_of_set] )
       // Case 2, for every set, you create a copy where you add 'a'
       for every set in list_of_set:
           response.push( [{set,'a'} + list_of_set\set] )

    // The function return the list of list of set created.        
    return(response)

Answer 2

有一个重要的观察（在评论中），一组 n 元素的分区可以表示为 [p 形式的整数序列₁, ... p_n] 其中 p_i是元素i的分区数。为了使这样的序列有效，它必须遵守 p₁ 为 1 的规则，并且对于每个 j，其中 1 < j ≤ n，有一些 i < j 这样 p_j ≤ p_i+1。或者换句话说，在序列的任何前缀中，都没有跳过整数。

现在，有一个按字典顺序枚举约束序列的标准算法，它包括以下内容：

从最小的序列开始。
按字典顺序查找下一个序列：
- 向后扫描序列并找到最右边的 "incrementable" 元素。（可递增元素是这样一种元素，即有一些更大的元素可以替代该元素，并且到该点为止的结果子序列是至少一个有效序列的前缀。）
- 将该元素更改为下一个更大的可行元素（即产生有效前缀，如上所述），然后用尽可能小的值填充其右侧的剩余元素（如果有）。
- 如果没有可递增的元素，则枚举终止。

有几个关于搜索可递增元素的规定，这个算法在最坏的情况下是 O(n)，通常是 O(1) 当要递增的元素通常接近序列末尾时。（比如用这个算法枚举排列是O(1)，找到下一个排列只要能在O(1)中找到"next element"即可。）

为了将此算法应用于分区情况，我们观察到以下内容：

可能的最小序列是 [1, … 1]
元素 p_i 是可递增的，前提是：
- p_i<n
- 有些 j<i 这样 p_i=p_j
可行前缀的最小后缀是 [1, … 1]

另一种陈述观察 2 中的条件的方法是，一个元素是可递增的，除非它的值是 n 或者它是序列中具有它的值的第一个元素。如果我们还维护序列 [m₁, … m[=103，我们可以在 O(1) 中做出决定=]_n] 其中 m₁ 为 0， m_i 是 m[= 的最大值70=]i-1 和 p_{i- 1}。 m 维护起来很简单，它允许我们将可增量条件重写为简单的 p_i≤m_i.

很容易看出Next Partition可以在O(n)时间内实现，但恰好也是如果它是摊销时间 O(1)。粗略地说，这是因为在大多数情况下，序列的最后一个元素是可递增的。

Answer 3

我正在研究一种有效的算法，该算法根据@rici 定义的关键字方法生成一个集合的所有分区，如前所述。下面的算法，用 python 编写，可以做到，并且仍有优化的可能。我去做。您可能知道，这个问题是 NP 完全问题！由于优化，可能会有一些奇怪的符号，如 try/except。然而，n 和 k 变量是通过 n 来定义的，集合有多少个不同的元素，k 是集合允许具有的不同类的数量。信息：该算法生成的所有分区最多为不同类的数量，而不仅仅是那些类!!!

def partitions():
        global n
        global k
        codeword = [1 for digitIndex in range(0, n)]
        while True:
                print codeword
                startIndex = n - 1
                while startIndex >= 0:
                        maxValue = max(codeword[0 : startIndex])
                        if codeword[startIndex] > maxValue or maxValue > k or codeword[startIndex] >= k:
                                codeword[startIndex] = 1
                                startIndex -= 1
                        else:
                                codeword[startIndex] += 1
                                break

n = 12
k = 2
try:
        partitions()
except:
        pass

生成集合的所有分区

generate all partitions of a set

algorithm

set

combinatorics

backtracking