生成集合的所有分区 [英] generate all partitions of a set

问题描述

对于一组格式为 A = {1,2,3，...，n} 的集合。这称为集合 A 的分区，集合<< c $ c> k <= n 的元素遵循以下定理：

For a set of the form A = {1, 2, 3, ..., n}. It is called partition of the set A, a set of k<=n elements which respect the following theorems:

a） A 的所有分区的并集为 A

a) the union of all the partitions of A is A

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

b) the intersection of 2 partitions of A is the empty set (they can't share the same elements).

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

For example. A = {1, 2,... n} We have the partitions: {1, 2, 3} {1, 2} {3} {1, 3} {2} {2, 3} {1} {1} {2} {3}

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

These theoretical concepts are presented in my algorithms textbook (by the way, this subchapter is part of the "Backtracking" chapter). I am supposed to find an algorithm to generate all the partitions of a given set. I was struggling with this problem all the day and I couldn't find a solution. Can you explain me how does this algorithm work? Also, can you give me a pseudo-code sketch of the algorithm?

推荐答案

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

You can try the recursive answer if your set is not to big (or else use stack) :

原理如下，您有一个可以回馈的函数：

The principle is the following, you have a function that give back :

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)

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