我需要一种算法来查找集合中元素数量为 的集合的所有子集n。
S={1,2,3,4...n}
编辑：到目前为止，我无法理解提供的答案。我想逐步解释答案如何找到子集。
例如，
S={1,2,3,4,5}
你怎么知道{1}并且{1,2}是子集？
有人可以帮我用 C++ 中的一个简单函数来查找 {1,2,3,4,5} 的子集吗
问问题
119333 次
22 回答
112
递归地执行此操作非常简单。基本思想是，对于每个元素，子集的集合可以平均分为包含该元素的子集和不包含该元素的子集，否则这两个集合是相等的。
- 对于 n=1，子集的集合是 {{}, {1}}
- 对于 n>1，找到 1,...,n-1 的子集的集合并制作两个副本。对于其中一个，将 n 添加到每个子集。然后取两个副本的并集。
编辑使其一目了然：
- {1} 的子集是 {{}, {1}}
- 对于 {1, 2}，取 {{}, {1}}，每个子集加 2 得到 {{2}, {1, 2}} 并取与 {{}, {1}} 的并集得到{{}、{1}、{2}、{1、2}}
- 重复直到达到 n
于 2009-04-08T11:38:16.173 回答
58
回答太晚了，但迭代方法在这里听起来很容易：
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) 得到 的二进制表示2^n。例如：
8 in binary is 1000
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) 对步骤 3 中找到的所有子集进行并集。返回。例如：
Simple union of above sets!
于 2012-09-25T17:52:49.547 回答
29
万一其他人过来仍然想知道，这里有一个使用迈克尔在 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 的所有可能子集，这意味着可能会有重复。如果您不想要这个，我建议实际使用 aset而不是 a vector（我曾经使用它来避免代码中的迭代器）。
于 2013-05-01T00:09:32.780 回答
9
如果您想列举所有可能的子集，请查看本文。他们讨论了不同的方法，例如字典顺序、格雷编码和银行家序列。他们给出了银行家序列的示例实现，并讨论了解决方案的不同特征，例如性能。
于 2009-04-08T08:15:12.263 回答
6
在这里，我已经详细解释过了。如果您喜欢这篇博文，请点赞。
http://cod3rutopia.blogspot.in/
如果你在这里找不到我的博客，无论如何都是解释。
这是一个本质上是递归的问题。
本质上，对于要出现在子集中的元素，有 2 个选项：
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)
}
}
于 2013-07-14T18:58:57.243 回答
4
自底向上 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);
}
于 2015-02-02T09:42:40.613 回答
4
这是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
于 2015-03-15T11:22:15.703 回答
4
这是 Michael 针对 std::vector 中任何类型元素的解决方案的实现。
#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
于 2015-10-28T02:43:39.747 回答
4
一个优雅的递归解决方案，对应于上面的最佳答案解释。核心向量运算只有 4 行。归功于安蒂的 Laaksonen 的“竞争编程指南”一书。
// #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);
}
于 2018-10-28T15:59:22.567 回答
3
你不必弄乱递归和其他复杂的算法。您可以使用 0 到 2^(N-1) 之间的所有数字的位模式（十进制到二进制）找到所有子集。这里 N 是该集合中的基数或项目数。此处通过实现和演示解释了该技术。
于 2010-10-01T12:07:10.307 回答
2
这是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)
}
于 2010-10-24T04:35:07.793 回答
2
这是一些伪代码。您可以通过存储每次调用的值来减少相同的递归调用，然后在递归调用检查调用值是否已经存在之前。
以下算法将具有除空集之外的所有子集。
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;
}
}
于 2013-02-16T01:45:32.900 回答
2
这是我前段时间写的一个工作代码
// Return all subsets of a given set
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
#include<cstring>
#include<climits>
#include<cmath>
#include<iterator>
#include<set>
#include<map>
#include<stack>
#include<queue>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< vector<int> > vvi;
typedef vector<string> vs;
vvi get_subsets(vi v, int size)
{
if(size==0) return vvi(1);
vvi subsets = get_subsets(v,size-1);
vvi more_subsets(subsets);
for(typeof(more_subsets.begin()) it = more_subsets.begin(); it !=more_subsets.end(); it++)
{
(*it).push_back(v[size-1]);
}
subsets.insert(subsets.end(), (more_subsets).begin(), (more_subsets).end());
return subsets;
}
int main()
{
int ar[] = {1,2,3};
vi v(ar , ar+int(sizeof(ar)/sizeof(ar[0])));
vvi subsets = get_subsets(v,int((v).size()));
for(typeof(subsets.begin()) it = subsets.begin(); it !=subsets.end(); it++)
{
printf("{ ");
for(typeof((*it).begin()) it2 = (*it).begin(); it2 !=(*it).end(); it2++)
{
printf("%d,",*it2 );
}
printf(" }\n");
}
printf("Total subsets = %d\n",int((subsets).size()) );
}
于 2013-07-08T12:58:06.283 回答
1
这个问题很老了。但是对于 OP 的问题，有一个简单优雅的递归解决方案。
using namespace std;
void recsub(string sofar, string rest){
if(rest=="") cout<<sofar<<endl;
else{
recsub(sofar+rest[0], rest.substr(1)); //including first letter
recsub(sofar, rest.substr(1)); //recursion without including first letter.
}
}
void listsub(string str){
recsub("",str);
}
int main(){
listsub("abc");
return 0;
}
//output
abc
ab
ac
a
bc
b
c
//end: there's a blank output too representing empty subset
于 2017-04-10T18:35:12.403 回答
0
一种简单的方法是以下伪代码：
Set getSubsets(Set theSet)
{
SetOfSets resultSet = theSet, tempSet;
for (int iteration=1; iteration < theSet.length(); iteration++)
foreach element in resultSet
{
foreach other in resultSet
if (element != other && !isSubset(element, other) && other.length() >= iteration)
tempSet.append(union(element, other));
}
union(tempSet, resultSet)
tempSet.clear()
}
}
好吧，我不确定这是否正确，但看起来还可以。
于 2009-04-08T13:50:58.803 回答
0
这是我的递归解决方案。
vector<vector<int> > getSubsets(vector<int> a){
//base case
//if there is just one item then its subsets are that item and empty item
//for example all subsets of {1} are {1}, {}
if(a.size() == 1){
vector<vector<int> > temp;
temp.push_back(a);
vector<int> b;
temp.push_back(b);
return temp;
}
else
{
//here is what i am doing
// getSubsets({1, 2, 3})
//without = getSubsets({1, 2})
//without = {1}, {2}, {}, {1, 2}
//with = {1, 3}, {2, 3}, {3}, {1, 2, 3}
//total = {{1}, {2}, {}, {1, 2}, {1, 3}, {2, 3}, {3}, {1, 2, 3}}
//return total
int last = a[a.size() - 1];
a.pop_back();
vector<vector<int> > without = getSubsets(a);
vector<vector<int> > with = without;
for(int i=0;i<without.size();i++){
with[i].push_back(last);
}
vector<vector<int> > total;
for(int j=0;j<without.size();j++){
total.push_back(without[j]);
}
for(int k=0;k<with.size();k++){
total.push_back(with[k]);
}
return total;
}
}
于 2013-09-10T15:54:23.933 回答
0
如前所述，一个简单的位掩码可以解决问题.... by rgamber
#include<iostream>
#include<cstdio>
#define pf printf
#define sf scanf
using namespace std;
void solve(){
int t; char arr[99];
cin >> t;
int n = t;
while( t-- )
{
for(int l=0; l<n; l++) cin >> arr[l];
for(int i=0; i<(1<<n); i++)
{
for(int j=0; j<n; j++)
if(i & (1 << j))
pf("%c", arr[j]);
pf("\n");
}
}
}
int main() {
solve();
return 0;
}
于 2015-03-26T14:49:14.967 回答
0
对于那些想要使用 std::vector 和 std::set 来实现 Michael Borgwardt 算法的简单实现的人：
// Returns the subsets of given set
vector<set<int> > subsets(set<int> s) {
vector<set<int> > s1, s2;
set<int> empty;
s1.push_back(empty); // insert empty set
// iterate over each element in the given set
for(set<int>::iterator it=s.begin(); it!=s.end(); ++it) {
s2.clear(); // clear all sets in s2
// create subsets with element (*it)
for(vector<set<int> >::iterator s1iter=s1.begin(); s1iter!=s1.end(); ++s1iter) {
set<int> temp = *s1iter;
temp.insert(temp.end(), *it);
s2.push_back(temp);
}
// update s1 with new sets including current *it element
s1.insert(s1.end(), s2.begin(), s2.end());
}
// return
return s1;
}
于 2015-11-14T22:31:56.677 回答
0
vector<vetor<int>> subarrays(vector<int>& A) {
vector<vetor<int>> set;
vector<vector<int>> tmp;
set.push_back({});
set.push_back({});
set[1].push_back(A[0]);
for(int i=1;i<A.size();i++){
tmp=set;
for(int j=0;j<tmp.size();j++){
tmp[j].push_back(A[i]);
}
set.insert( set.end(), tmp.begin(), tmp.end() );
}
return set;
}
于 2021-03-07T01:07:14.523 回答
0
这是按照原始答案的代码
void print_subsets(std::vector<int>& nums, int i, std::vector<std::vector<int>>& results, std::vector<int>& r) {
if (i < nums.size()) {
r.push_back(nums[i]); // First consider the element
print_subsets(nums, i + 1, results, r);
r.pop_back(); // Now don't consider the element
print_subsets(nums, i + 1, results, r);
}
else {
results.push_back(r);
}
}
// Main method
vector<vector<int>> subsets(vector<int>& nums) {
std::vector<std::vector<int>> results;
std::vector<int> r;
print_subsets(nums, 0, results, r);
return results;
}
于 2021-03-21T17:22:09.503 回答
0
根据公认的 Swift 中的递归解决方案：
private func getSubsets(_ set: Set<Int>) -> Set<Set<Int>> {
var set = set // Allows you to manipulate the set
if set.isEmpty { // Base Case: Subset of an empty set is an empty set
return [[]]
} else { // Remove n, find subset of 1,...,n - 1, duplicate subset and append n to duplicated set, return the union of both
let n = set.removeFirst()
var subset = getSubsets(set)
for i in subset {
var temp = i
temp.insert(n)
subset.insert(temp)
}
return subset
}
}
于 2021-06-08T02:12:51.723 回答
0
基于上述“Michael Borgwardt”算法的无递归Java 版本。
public static List<List> powerset(List array) { List<List> perms = new ArrayList<List>(); if(array.size()==0) { perms.add(new ArrayList()); 退货烫发；} 返回幂集（数组，烫发）；}
public static List<List<Integer>> powerset(List<Integer> array, List<List<Integer>> perms) {
for(int i=0;i<array.size();i++){
perms.add(Arrays.asList(array.get(i)));
int x=perms.size();
for(int j=0;j<x;j++){
List<Integer> tmp = new ArrayList<Integer>(perms.get(j));
if(!(tmp.size()==1 && tmp.get(0)==array.get(i))){
tmp.add(array.get(i));
perms.add(tmp);
}
}
}
perms.add(new ArrayList<Integer>());
return perms;
}
于 2022-01-22T15:38:24.800 回答