これを再帰的に行うのは非常に簡単です。基本的な考え方は、各要素について、サブセットのセットをその要素を含むものと含まないものに均等に分割でき、それ以外の点ではこれら2つのセットは等しいということです。
編集それを明確にするために：
答えるには遅すぎますが、ここでは反復アプローチが簡単に思えます。
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!
他の誰かが来て、まだ疑問に思っている場合に備えて、C++ での Michael の説明を使用した関数を次に示します。
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 のセットを返すことを考慮してください。つまり、重複する可能性があります。これが望ましくない場合は、実際には a のset代わりに aを使用することをお勧めvectorします (コード内の反復子を避けるために使用していました)。
可能なすべてのサブセットを列挙したい場合は、このペーパーをご覧ください。彼らは、辞書編集順序、グレイ コーディング、バンカー シーケンスなどのさまざまなアプローチについて説明しています。彼らは、バンカーのシーケンスの実装例を示し、パフォーマンスなどのソリューションのさまざまな特性について説明しています。
ここまで詳しく解説してきました。ブログ投稿が気に入ったら、賛成票を投じてください。
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)
}
}
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);
}
これは、セットのすべてのサブセットを見つけるための 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])
出力は次のようになります。
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
上記のベストアンサーの説明に対応する洗練された再帰的ソリューション。コアのベクトル演算はわずか 4 行です。Antti の Laaksonen による "Guide to Competitive Programming" 本のクレジットです。
// #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);
}
再帰やその他の複雑なアルゴリズムをいじる必要はありません。0 から 2^(N-1) までのすべての数値のビット パターン (10 進数から 2 進数) を使用して、すべてのサブセットを見つけることができます。ここで、N はそのセット内のカーディナリティまたはアイテム数です。ここでは、実装とデモを使用してこの手法について説明します。
これは私がしばらく前に書いた作業コードです
// 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()) );
}
ここにいくつかの擬似コードがあります。呼び出し値が既に存在するかどうかを確認する再帰呼び出しの前に、各呼び出しの値を保存することで、同じ再帰呼び出しをカットできます。
次のアルゴリズムには、空のセットを除くすべてのサブセットが含まれます。
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;
}
}
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)
}
簡単な方法の 1 つは、次の疑似コードです。
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()
}
}
これが正しいかどうかは完全にはわかりませんが、問題ないようです。
Michael Borgwardt のアルゴリズムに std::vector と std::set を使用した単純な実装が必要な場合:
// 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;
}
元の回答によるコードは次のとおりです
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;
}