生成集合的所有分区

一尘不染

生成集合的所有分区

algorithm

为一组表格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}

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

阅读 293

2020-07-28

共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)

2020-07-28