生成集合的所有分区

Question

对于一组表格A = {1, 2, 3, ..., n}.它被称为集合的分区,是A一组k<=n尊重以下定理的元素:

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

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

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

这些理论概念在我的算法教科书中提出(顺便说一下,这个子章节是"回溯"章节的一部分).我应该找到一个算法来生成给定集合的所有分区.我整天都在努力解决这个问题,但我找不到解决办法.你能解释一下这个算法是如何工作的吗？另外,你能给我一个算法的伪代码草图吗？

Answer 1

有一个重要的观察结果(在评论中),一组n元素的分区可以表示为[ p ₁,... p _n ] 形式的整数序列,其中p _i是元素i的分区号.对于这样的序列是有效的,它必须遵守的规则p ₁是1,并且对于每个Ĵ其中1 < Ĵ ≤ Ñ,有一些我 < Ĵ使得p _Ĵ ≤ p _我 1.或者换句话说,在序列的任何前缀中,不会跳过整数.

现在,有一种用于按字典顺序枚举约束序列的标准算法,包括以下内容:

• 从最小的序列开始.
• 要按字典顺序查找下一个序列:
  • 向后扫描序列并找到最右边的"可递增"元素.(可递增元素是一个元素,使得有一些更大的元素可以替换该元素,并且到此为止的结果子序列是至少一个有效序列的前缀.)
  • 将该元素更改为可行的下一个更大的元素(即导致有效前缀,如上所述),然后用尽可能小的值填充其右侧的剩余元素(如果有的话).
  • 如果没有可递增元素,则枚举已终止.

关于搜索可递增元素的若干规定,该算法最差O(n),并且当要递增的元素通常接近序列的末尾时通常为O(1).(例如,使用此算法枚举置换是O(1)以找到下一个置换,只要您可以在O(1)中找到"下一个元素".)

为了将此算法应用于分区案例,我们观察以下内容:

1. 最小的序列是[1,... 1]
2. 元素p _i是可递增的,条件是:
   • p _i < n
   • 有一些j < i,使得p _i = p _j
3. 可行前缀的最小后缀是[1,... 1]

说明观察2中的条件的另一种方式是元素是可递增的,除非它的值是n或者它是序列中具有其值的第一个元素.如果我们也保持序列[ m ₁,... m _n ],其中m ₁是0,并且m _i是m _{i -1}和p _{i -1}的最大值,我们可以在O(1)中进行该确定.米是微不足道的维护,并且它允许我们重写被简称为incrementability条件p _我 ≤ 中号_我.

很容易看出Next Partition可以在O(n)时间内实现,但是当它发生时,它也是分摊时间O(1)的情况.粗略地说,这是因为在大多数情况下,序列的最后一个元素是可递增的.

Answer 2

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

原理如下，你有一个返回的函数：

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)