寻找一个集合的所有子集

Question

我需要一个算法来查找集合中元素数量为n的所有子集。

S={1,2,3,4...n}

编辑：我现在还不太明白已经提供的答案，希望能够逐步解释一下如何通过这些答案来找到子集。

例如：

S={1,2,3,4,5}

如何判断 {1} 和 {1,2} 是否为子集？

能否有人帮我写一个简单的C++函数，用于查找 {1,2,3,4,5} 的子集。

- Rahul Vyas

---

这个问题相当模糊，你是指所有可能的子集吗？ - sris

子集的数量不是n!，这是排列的数量。子集的数量（幂集的基数）是2^n。 - sris

Answer 1

这可以采用递归的方式实现。基本思路是对于每个元素，将其子集分为包含该元素和不包含该元素的两部分，并且这两个子集除了包含或不包含该元素外相同。

• 当n=1时，子集列表为{{}, {1}}
• 当n>1时，找到1,...,n-1的子集列表并将其复制一份，对其中一个副本中的每个子集都添加n。然后将两个副本合并。

编辑：更加清晰地说明：

• {1}的子集列表为{{}, {1}}
• 对于{1, 2}，取{{}, {1}}，在其中的每个子集中加入2，得到{{2}, {1, 2}}，再将其与{{}, {1}}合并，得到{{}, {1}, {2}, {1, 2}}
• 重复上述步骤，直至达到n

- Michael Borgwardt

---

谢谢，但我仍然不知道如何将2添加到每个子集中，以及如何取并集......您能否用这个集合描述一下？{1,2,3,4,5}请按以下步骤进行操作：

1. 添加2到每个子集。例如，对于子集{1,3,5}，将其变为{1,2,3,5,}。
2. 要计算该集合的并集，请将所有子集组合在一起。对于此集合，所有可能的子集为：

{1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}, {1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}将它们组合在一起，即为并集。 - Rahul Vyas

真正的初始情况应该是“空集的幂集是{{}}”。然后{n}的幂集是{{}}并集{n}。以此类推。 - Ingo

是的，但我认为这样更容易理解。 - Michael Borgwardt

任何正在寻找JavaScript代码的人可以访问以下链接：link - talal7860

这里是一个晚回答：一种优雅的递归解决方案，与上面的解释相对应。核心向量操作仅有4行代码。感谢拉克松恩（Antti Laaksonen）的《竞赛编程指南》一书。请在下面的答案中查看代码 https://dev59.com/yXRB5IYBdhLWcg3wET1J#53033401 - Eric Q

Answer 2

虽然回答有些晚了，但这里可以采用迭代方法：

1）对于一个包含 n 个元素的集合，获取 2^n 的值。它将会有 2^n 种子集。（2^n 是因为每个元素都可以存在（1）或不存在（0），因此对于 n 个元素，将会有 2^n 种子集）。例如：
对于3个元素，比如 {a,b,c}，则有2^3=8种子集

2）获取 2^n 的二进制表示。例如：
8 的二进制表示是1000

3）从 0 到 (2^n - 1) 进行循环迭代。在每次迭代中，对于二进制表示中的每个 1，在相应的索引处形成一个子集。例如：

For the elements {a, b, c}
000 will give    {}
001 will give    {c}
010 will give    {b}
011 will give    {b, c}
100 will give    {a}
101 will give    {a, c}
110 will give    {a, b}
111 will give    {a, b, c}

4) 对第3步中找到的所有子集进行并集操作。返回结果。例如：
对以上集合进行简单并集操作！

- rgamber

---

你的解决方案如何处理 n > 32 的情况？我猜你是在一个“int”中保存了 2^n。是这样吗？ - Elad Benda

抱歉，我还没有编写任何实现上述内容的代码，但是对于n>32，使用int32会有问题：）。Michael Borgwardt在上面提到了另一种解决方案。 - rgamber

我们可以使用大小为n的位数组（bit array）代替整数，并将其用于遍历所有子集。如果有人感兴趣，我可以在这里发布我的答案。 - Nitin Garg

对于任何实际的原因，long将足够长。 - talex

Answer 3

如果有其他人经过并且仍然想知道，这是一个使用Michael在C++中解释的函数

vector< vector<int> > getAllSubsets(vector<int> set)
{
    vector< vector<int> > subset;
    vector<int> empty;
    subset.push_back( empty );

    for (int i = 0; i < set.size(); i++)
    {
        vector< vector<int> > subsetTemp = subset;  //making a copy of given 2-d vector.

        for (int j = 0; j < subsetTemp.size(); j++)
            subsetTemp[j].push_back( set[i] );   // adding set[i] element to each subset of subsetTemp. like adding {2}(in 2nd iteration  to {{},{1}} which gives {{2},{1,2}}.

        for (int j = 0; j < subsetTemp.size(); j++)
            subset.push_back( subsetTemp[j] );  //now adding modified subsetTemp to original subset (before{{},{1}} , after{{},{1},{2},{1,2}}) 
    }
    return subset;
}

不过需要注意的是，这将返回大小为2 ^ N的包含所有可能子集的集合，这意味着可能会有重复项。如果你不想要重复项，我建议实际使用set而不是vector（我在代码中避免迭代器使用了vector）。

- Ronald Rey

---

在我看来，这是最佳答案。我将代码转换为C#以便更好地理解它，在这里查看：http://ideone.com/bnWlcM - reggaeguitar

Ronald Rey的回答很有帮助。 在此处提供完整的C++源代码/实现：http://ideone.com/fork/b3VjD9 - Akshay

@AkshaySarkar 谢谢！很高兴能帮到你。 - Ronald Rey

Answer 4

如果您想枚举所有可能的子集，请查看这篇论文。他们讨论了不同的方法，如字典序、格雷编码和银行家序列。他们提供了银行家序列的示例实现，并讨论了解决方案的不同特性，例如性能。

- sris

Answer 5

我在这里详细解释了它。如果你喜欢这篇博客文章，请点赞。

http://cod3rutopia.blogspot.in/

如果你找不到我的博客，这里是解释。

这是一个递归性质的问题。

基本上，对于一个元素存在于子集中有两个选项：

1)它存在于集合中

2)它不存在于集合中。

这就是为什么一个由n个数字组成的集合有2^n个子集的原因。(每个元素有2个选项)

下面是打印所有子集的伪代码(C++)，并且附带一个例子来说明代码的工作原理。 1)A[]是要查找其子集的数字数组。 2)bool a[]是布尔数组，其中a[i]表示数字A[i]是否存在于集合中。

print(int A[],int low,int high)  
   {
    if(low>high)  
    {
     for(all entries i in bool a[] which are true)  
        print(A[i])
    }  
   else  
   {set a[low] to true //include the element in the subset  
    print(A,low+1,high)  
    set a[low] to false//not including the element in the subset  
    print(A,low+1,high)
   }  
  }  

- Jaskaran

---

如果博客不再在线上了呢？或者只是因为维护而暂时关闭了呢？请在您的回答中提供源代码，而不是链接。 - Manuel

好的，Manuel，但问题是我不想仅仅提供源代码。我有一份解释，并且我不想再重新写一遍所有的东西。 - Jaskaran

如果您的博客文章已经解释了一切，那么只需复制粘贴即可吗？ - Manuel

我已经做出了更改。 - Jaskaran

Answer 6

以下是一个简单的Python递归算法，用于查找一个集合的所有子集：

def find_subsets(so_far, rest):
        print 'parameters', so_far, rest
        if not rest:
            print so_far
        else:
            find_subsets(so_far + [rest[0]], rest[1:])
            find_subsets(so_far, rest[1:])


find_subsets([], [1,2,3])

输出结果如下： $python subsets.py

parameters [] [1, 2, 3]
parameters [1] [2, 3]
parameters [1, 2] [3]
parameters [1, 2, 3] []
[1, 2, 3]
parameters [1, 2] []
[1, 2]
parameters [1] [3]
parameters [1, 3] []
[1, 3]
parameters [1] []
[1]
parameters [] [2, 3]
parameters [2] [3]
parameters [2, 3] []
[2, 3]
parameters [2] []
[2]
parameters [] [3]
parameters [3] []
[3]
parameters [] []
[]

请观看斯坦福大学的以下视频，了解这个算法的详细解释：

https://www.youtube.com/watch?v=NdF1QDTRkck&feature=PlayList&p=FE6E58F856038C69&index=9

- user847988

Answer 7

使用O(n)的空间自底向上解决方案

#include <stdio.h>

void print_all_subset(int *A, int len, int *B, int len2, int index)
{
    if (index >= len)
    {
        for (int i = 0; i < len2; ++i)
        {
            printf("%d ", B[i]);
        }
        printf("\n");

        return;
    }
    print_all_subset(A, len, B, len2, index+1);

    B[len2] = A[index];
    print_all_subset(A, len, B, len2+1, index+1);
}



int main()
{
    int A[] = {1, 2, 3, 4, 5, 6, 7};
    int B[7] = {0};

    print_all_subset(A, 7, B, 0, 0);
}

- BB Chung

Answer 8

一种优雅的递归解决方案，对应于上面最佳答案解释。核心向量操作仅有4行。感谢来自Laaksonen, Antti的“竞赛编程指南”书籍。

// #include <iostream>
#include <vector>
using namespace std;

vector<int> subset;
void search(int k, int n) {
    if (k == n+1) {
    // process subset - put any of your own application logic
    // for (auto i : subset) cout<< i << " ";
    // cout << endl;
    }
    else {
        // include k in the subset
        subset.push_back(k);
        search(k+1, n);
        subset.pop_back();
        // don't include k in the subset
        search(k+1,n);
    }
}

int main() {
    // find all subset between [1,3]
    search(1, 3);
}

- Eric Q

Answer 9

这是一个针对std::vector中任意元素类型的Michael解决方案实现。

#include <iostream>
#include <vector>

using std::vector;
using std::cout;
using std::endl;

// Find all subsets
template<typename element>
vector< vector<element> > subsets(const vector<element>& set)
{
  // Output
  vector< vector<element> > ss;
  // If empty set, return set containing empty set
  if (set.empty()) {
    ss.push_back(set);
    return ss;
  }

  // If only one element, return itself and empty set
  if (set.size() == 1) {
    vector<element> empty;
    ss.push_back(empty);
    ss.push_back(set);
    return ss;
  }

  // Otherwise, get all but last element
  vector<element> allbutlast;
  for (unsigned int i=0;i<(set.size()-1);i++) {
    allbutlast.push_back( set[i] );
  }
  // Get subsets of set formed by excluding the last element of the input set
  vector< vector<element> > ssallbutlast = subsets(allbutlast);
  // First add these sets to the output
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ss.push_back(ssallbutlast[i]);
  }
  // Now add to each set in ssallbutlast the last element of the input
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ssallbutlast[i].push_back( set[set.size()-1] );
  }
  // Add these new sets to the output
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ss.push_back(ssallbutlast[i]);
  }

  return ss;

}

// Test
int main()
{

  vector<char> a;
  a.push_back('a');
  a.push_back('b');
  a.push_back('c');


  vector< vector<char> > sa = subsets(a);

  for (unsigned int i=0;i<sa.size();i++) {
    for (unsigned int j=0;j<sa[i].size();j++) {
      cout << sa[i][j];
    }
    cout << endl;
  }

  return 0;

}

输出：

(empty line)
a
b
ab
c
ac
bc
abc

- sb933

Answer 10

你不需要涉及递归和其他复杂的算法。通过使用 0 到 2^(N-1) 中所有数字的位模式（十进制转二进制），你可以找到所有子集。这里的 N 是集合中项目的基数或数量。这种技术在这里得到了解释，并提供了实现和演示。 http://codeding.com/?article=12

- Prabu Arumugam