C++ 查找集合的所有子集
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/728972/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding all the subsets of a set
提问by Rahul Vyas
I need an algorithm to find all of the subsets of a set where the number of elements in a set is n.
我需要一种算法来查找集合中元素数为 的集合的所有子集n。
S={1,2,3,4...n}
Edit: I am having trouble understanding the answers provided so far. I would like to have step-by-step explanation of how the answers work to find the subsets.
编辑：我无法理解到目前为止提供的答案。我想逐步解释答案如何找到子集。
For example,
例如，
S={1,2,3,4,5}
How do you know {1}and {1,2}are subsets?
你怎么知道{1}并且{1,2}是子集？
Could someone help me with a simple function in c++ to find subsets of {1,2,3,4,5}
有人可以用 C++ 中的一个简单函数帮助我找到 {1,2,3,4,5} 的子集吗
回答by Michael Borgwardt
It's very simple to do this recursively. The basic idea is that for each element, the set of subsets can be divided equally into those that contain that element and those that don't, and those two sets are otherwise equal.
递归地执行此操作非常简单。基本思想是，对于每个元素，子集集合可以平均分为包含该元素的子集和不包含该元素的子集，否则这两个集合是相等的。
- For n=1, the set of subsets is {{}, {1}}
- For n>1, find the set of subsets of 1,...,n-1 and make two copies of it. For one of them, add n to each subset. Then take the union of the two copies.
- 对于 n=1，子集集合为 {{}, {1}}
- 对于 n>1，找到 1,...,n-1 的子集集合并制作它的两个副本。对于其中之一，将 n 添加到每个子集。然后取两个副本的并集。
EditTo make it crystal clear:
编辑使其清晰：
- The set of subsets of {1} is {{}, {1}}
- For {1, 2}, take {{}, {1}}, add 2 to each subset to get {{2}, {1, 2}} and take the union with {{}, {1}} to get {{}, {1}, {2}, {1, 2}}
- Repeat till you reach n
- {1} 的子集集合是 {{}, {1}}
- 对于{1, 2}，取{{}, {1}}，每个子集加2得到{{2}, {1, 2}}，并与{{}, {1}}取并得到{{}、{1}、{2}、{1、2}}
- 重复直到达到 n
回答by rgamber
Too late to answer, but an iterative approach sounds easy here:
回答为时已晚，但迭代方法在这里听起来很容易：
1) for a set of nelements, get the value of 2^n. There will be 2^n no.of subsets. (2^n because each element can be either present(1) or absent(0). So for n elements there will be 2^n subsets. ). Eg:for 3 elements, say {a,b,c}, there will be 2^3=8 subsets
1) 对于一组n元素，获取 的值2^n。将有 2^n 个子集。（2^n 因为每个元素可以存在（1）或不存在（0）。因此对于 n 个元素，将有 2^n 个子集。）。例如：for 3 elements, say {a,b,c}, there will be 2^3=8 subsets
2) Get a binary representation of 2^n. Eg:8 in binary is 1000
2) 得到 的二进制表示2^n。例如：8 in binary is 1000
3) Go from 0to (2^n - 1). In each iteration, for each 1 in the binary representation, form a subset with elements that correspond to the index of that 1 in the binary representation.
Eg:
3) 从0到(2^n - 1)。在每次迭代中，对于二进制表示中的每个 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) Do a union of all the subsets thus found in step 3. Return. Eg:Simple union of above sets!
4) 对在步骤 3 中找到的所有子集进行联合。返回。例如：Simple union of above sets!
回答by Ronald Rey
In case anyone else comes by and was still wondering, here's a function using Michael's explanation in C++
如果其他人来了仍然想知道，这里有一个使用迈克尔在 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;
}
Take into account though, that this will return a set of size 2^N with ALL possible subsets, meaning there will possibly be duplicates. If you don't want this, I would suggest actually using a setinstead of a vector(which I used to avoid iterators in the code).
不过要考虑到，这将返回一组大小为 2^N 的集合，其中包含所有可能的子集，这意味着可能会有重复。如果你不想要这个，我建议实际上使用 aset而不是 a vector（我曾经在代码中避免使用迭代器）。
回答by sris
If you want to enumerate all possible subsets have a look at thispaper. They discuss different approaches such as lexicographical order, gray coding and the banker's sequence. They give an example implementation of the banker's sequence and discuss different characteristics of the solutions e.g. performance.
如果要列举所有可能的子集来看看这个文件。他们讨论了不同的方法，例如字典顺序、格雷编码和银行家序列。他们给出了银行家序列的示例实现，并讨论了解决方案的不同特性，例如性能。
回答by Jaskaran
Here, I've explained it in detail. Do upvote, if you like the blogpost.
在这里，我已经详细解释了。如果你喜欢这篇博文，请点赞。
http://cod3rutopia.blogspot.in/
http://cod3rutopia.blogspot.in/
Any way if you can't find my blog here is the explanation.
如果你在这里找不到我的博客，无论如何都是解释。
Its a problem which is recursive in nature.
这是一个本质上递归的问题。
Essentially for an element to be present in a subset there are 2 options:
本质上，对于要出现在子集中的元素，有 2 个选项：
1)It is present in the set
1）它存在于集合中
2)It is absent in the set.
2) 集合中不存在。
This is the reason why a set of n numbers has 2^n subsets.(2 options per element)
这就是为什么一组 n 个数字有 2^n 个子集的原因。（每个元素 2 个选项）
Here is the pseudo-code(C++) to print all the subsets followed by an example explaining how the code works. 1)A[] is the array of numbers whose subsets you want to find out. 2) bool a[] is the array of booleans where a[i] tells whether the number A[i] is present in the set or not.
这是打印所有子集的伪代码（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)
}
}
回答by user847988
Here is a simple recursive algorithm in python for finding all subsets of a set:
这是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])
The output will be the following: $python subsets.py
输出如下：$python subnets.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 [] []
[]
Watch the following video from Stanford for a nice explanation of this algorithm:
观看以下来自斯坦福的视频，以获得对该算法的一个很好的解释：
https://www.youtube.com/watch?v=NdF1QDTRkck&feature=PlayList&p=FE6E58F856038C69&index=9
回答by sbalian
Here is an implementation of Michael's solution for any type of element in std::vector.
这是针对 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;
}
Output:
输出：
(empty line)
a
b
ab
c
ac
bc
abc
回答by Prabu Arumugam
You dont have to mess with recursion and other complex algorithms. You can find all subsets using bit patterns (decimal to binary) of all numbers between 0 and 2^(N-1). Here N is cardinality or number-of-items in that set. The technique is explained here with an implementation and demo.
你不必搞乱递归和其他复杂的算法。您可以使用 0 到 2^(N-1) 之间的所有数字的位模式（十进制到二进制）找到所有子集。这里 N 是该集合中的基数或项目数。此处通过实现和演示解释了该技术。
回答by cayhorstmann
Here is a solution in Scala:
这是Scala中的解决方案：
def subsets[T](s : Set[T]) : Set[Set[T]] =
if (s.size == 0) Set(Set()) else {
val tailSubsets = subsets(s.tail);
tailSubsets ++ tailSubsets.map(_ + s.head)
}
回答by kofhearts
Here's some pseudocode. You can cut same recursive calls by storing the values for each call as you go and before recursive call checking if the call value is already present.
这是一些伪代码。您可以通过在执行过程中以及在递归调用检查调用值是否已经存在之前存储每个调用的值来减少相同的递归调用。
The following algorithm will have all the subsets excluding the empty set.
以下算法将包含除空集之外的所有子集。
list * subsets(string s, list * v){
if(s.length() == 1){
list.add(s);
return v;
}
else
{
list * temp = subsets(s[1 to length-1], v);
int length = temp->size();
for(int i=0;i<length;i++){
temp.add(s[0]+temp[i]);
}
list.add(s[0]);
return temp;
}
}
