C# 如何找到给定数组的所有可能子集？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/679203/
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
How to find all possible subsets of a given array?
提问by Mobin
I want to extract all possible sub-sets of an array in C# or C++ and then calculate the sum of all the sub-set arrays' respective elements to check how many of them are equal to a given number.
我想在 C# 或 C++ 中提取数组的所有可能子集，然后计算所有子集数组各自元素的总和，以检查它们中有多少等于给定数字。
What I am looking for is the algorithm. I do understand the logic here but I have not been able to implement this one by now.
我正在寻找的是算法。我确实理解这里的逻辑，但我现在还没有能够实现这个逻辑。
回答by Pete Kirkham
Considering a set Sof Nelements, and a given subset, each element either does or doesn't belong to that subset. Therefore are 2^Npossible subsets (if you include the original and empty sets), and there is a direct mapping from the bits in the binary representation of xbetween 0and 2^Nto the elements in the xth subset of S.
考虑一组S的N元素，和给定子集，各元素或者不或不属于该子集。因此是2^N可能的子集（如果包括原始集和空集），并且存在从xbetween0和的二进制表示中的位2^N到 的xth 子集中的元素的直接映射S。
Once you've worked out how to enumerate the elements of a given subset, adding the values is simple.
一旦确定了如何枚举给定子集的元素，添加值就很简单了。
For finding subsets which equal a total tfor large N, one optimisation might be to record those subsets which exceed t, and not test any which are proper supersets of those. Testing whether set number xis a superset of set ycan be achieved with a single bitwise operation and an integer comparison.
为了找到t与 large的总和相等的子集N，一种优化可能是记录那些超过 的子集t，而不测试任何是这些子集的正确超集。可以通过单个按位运算和整数比较来测试集合编号是否是集合x的超集y。
回答by Andrew Grant
Do you;
你;
A) Really want to find all of the possible subsets?
A) 真的想找到所有可能的子集吗？
or
或者
B) Wish to find how many elements in an array can be combined to equal a given number, and see A) as a step towards the solution?
B) 希望找出一个数组中有多少个元素可以组合成一个给定的数字，并将 A) 视为解决方案的一个步骤？
If it's A) then it's quite straightforward but the number of possible subsets becomes ridiculously large very quickly.
如果是 A)，那么它很简单，但是可能的子集数量很快就会变得非常大。
If it's B) then you should sort the array first and work from there.
如果是 B) 那么你应该先对数组进行排序并从那里开始工作。
回答by sepehr
It's been one of my college projects 4/5 years ago, and I can't remind the algorithm well. As I see & my memory serves it's using an array as the original set and a bitmask to indicate what elements are present in the current subset.
here's the un-tested code from the archive:
这是我 4/5 年前的大学项目之一，我不能很好地提醒算法。正如我所见&我的记忆服务它使用一个数组作为原始集合和一个位掩码来指示当前子集中存在哪些元素。
这是存档中未经测试的代码：
#include <iostream>
#ifndef H_SUBSET
#define H_SUBSET
template <class T>
class Subset {
private:
int Dimension;
T *Set;
bool *Bitmask;
public:
Subset(T *set, int dim);
~Subset(void);
void Show(void);
void NextSubset(void);
void EmptySet(void);
void FullSet(void);
int SubsetCardinality(void);
int SetCardinality(void);
T operator[](int index);
};
template <class T>
int Subset<T>::SetCardinality(void) {
return Dimension;
}
template <class T>
int Subset<T>::SubsetCardinality(void) {
int dim = 0;
for(int i = 0; i<Dimension; i++) {
if(Bitmask[i]) {
dim++;
}
}
return dim;
}
template <class T>
void Subset<T>::EmptySet(void) {
for(int i = 0; i<Dimension; i++) {
Bitmask[i] = 0;
}
return;
}
template <class T>
void Subset<T>::FullSet(void) {
for(int i = 0; i<Dimension; i++) {
Bitmask[i] = 1;
}
return;
}
template <class T>
void Subset<T>::NextSubset(void) {
int i = Dimension - 1;
while(!Bitmask[i]&&i>=0) {
i--;
if(i<0) {
break;
}
}
if(i>=0) {
Bitmask[i] = !Bitmask[i];
}
for(int j = i+1; j < Dimension; j++) {
Bitmask[j] = !Bitmask[j];
}
return;
}
template <class T>
void Subset<T>::Show(void) {
std::cout << "{ ";
for(int i=0; i<Dimension; i++) {
if(Bitmask[i]) {
std::cout << Set[i] << ", ";
}
}
std::cout << "}";
return;
}
template <class T>
Subset<T>::Subset(T *set, int dim) {
Set = new T[dim];
Bitmask = new bool[dim];
Dimension = dim;
for(int i=0; i<dim; i++) {
Set[i] = set[i];
Bitmask[i] = true;
}
}
template <class T>
Subset<T>::~Subset(void) {
delete [] Set;
delete [] Bitmask;
}
#endif // H_SUBSET
And if it's your homework, you're killing yourself bro ;)
如果这是你的家庭作业，你就是在自杀，兄弟 ;)
回答by Bill the Lizard
What you're looking for is called the power set. Rosetta Codehas a lot of different implementations, but here's their C++ code (they use a vector instead of an array, but it should be pretty easy to translate).
您正在寻找的称为power set。 Rosetta Code有很多不同的实现，但这里是他们的 C++ 代码（他们使用向量而不是数组，但应该很容易翻译）。
#include <iostream>
#include <set>
#include <vector>
#include <iterator>
typedef std::set<int> set_type;
typedef std::set<set_type> powerset_type;
powerset_type powerset(set_type const& set)
{
typedef set_type::const_iterator set_iter;
typedef std::vector<set_iter> vec;
typedef vec::iterator vec_iter;
struct local
{
static int dereference(set_iter v) { return *v; }
};
powerset_type result;
vec elements;
do
{
set_type tmp;
std::transform(elements.begin(), elements.end(),
std::inserter(tmp, tmp.end()),
local::dereference);
result.insert(tmp);
if (!elements.empty() && ++elements.back() == set.end())
{
elements.pop_back();
}
else
{
set_iter iter;
if (elements.empty())
{
iter = set.begin();
}
else
{
iter = elements.back();
++iter;
}
for (; iter != set.end(); ++iter)
{
elements.push_back(iter);
}
}
} while (!elements.empty());
return result;
}
int main()
{
int values[4] = { 2, 3, 5, 7 };
set_type test_set(values, values+4);
powerset_type test_powerset = powerset(test_set);
for (powerset_type::iterator iter = test_powerset.begin();
iter != test_powerset.end();
++iter)
{
std::cout << "{ ";
char const* prefix = "";
for (set_type::iterator iter2 = iter->begin();
iter2 != iter->end();
++iter2)
{
std::cout << prefix << *iter2;
prefix = ", ";
}
std::cout << " }\n";
}
}
Output:
输出：
{ }
{ 2 }
{ 2, 3 }
{ 2, 3, 5 }
{ 2, 3, 5, 7 }
{ 2, 3, 7 }
{ 2, 5 }
{ 2, 5, 7 }
{ 2, 7 }
{ 3 }
{ 3, 5 }
{ 3, 5, 7 }
{ 3, 7 }
{ 5 }
{ 5, 7 }
{ 7 }
