迭代任意大小的子集

Question

我可以迭代大小为1的子集。

for( int a = 0; a < size; a++ ) {

或者大小为2的子集

for( int a1 = 0; a1 < size; a1++ ) {
    for( int a2 = a1+1; a2 < size; a2++ ) {

或3

for( int a1 = 0; a1 < size; a1++ ) {
for( int a2 = a1+1; a2 < size; a2++ ) {
   for( int a3 = a2+1; a3 < size; a3++ ) {

但是如何针对大小为n的子集执行此操作？

这个方法可以完成任务，基于Adam Rosenfield的答案。

void iterate(int *a, int i, int size, int n)
{
 int start = 0;
 if( i > 0 ) start = a[i-1]+1;
 for(a[i] = start; a[i] < n; a[i]++) {
  if(i == n-1) {
      // a is the array of indices of size n
      for( int k = 0; k < size; k++ ) {
          printf("%d ",a[k]);
      }
      printf("\n");
  }
        else
            iterate(a, i+1, size, n);
    }
}

- ravenspoint

---

你能否在你的回答中再加上一些注释呢？我可能有点慢，但我真的不太明白。 - Jekowl

Answer 1

您可以使用递归：

void iterate(int *a, int i, int size, int n)
{
    for(a[i] = 0; a[i] < size; a[i]++)
    {
        if(i == n-1)
            DoStuff(a, n);  // a is the array of indices of size n
        else
            iterate(a, i+1, size, n);
    }
}
...
// Equivalent to 4 nested for loops
int a[4];
iterate(a, 0, size, 4);

- Adam Rosenfield

---

这很有趣。然而，不强制执行i>j时a[i]>a[j]的条件。 - ravenspoint

但如果我添加了这个：int start = 0; if (i > 0) start = a[i-1]; for (a[i] = start; a[i] < size; a[i]++) - ravenspoint

糟糕！应该是int start = 0; if (i > 0) start = a[i-1] + 1; for (a[i] = start; a[i] < size; a[i]++) - ravenspoint

还需要再做一些改变。for循环的最大值应该是n，而不是size。有了这些改动，算法在生产代码中可以正常工作并通过单元测试！谢谢。 - ravenspoint

Answer 2

这是我用于类似问题的一些东西。它不使用递归，而是使用索引向量。

#include <vector>

template<class T>
class MultiForVar {
std::vector<T> _begin, _end, _vars;
inline int dim(){return _vars.size();}
public:
MultiForVar(std::vector<T> begin, std::vector<T> end) : _begin(begin), _end(end), _vars(_begin)
{
  assert(begin.size() == end.size() and "Starting and ending vector<T> not the same size!" );
}
MultiForVar& operator ++()
{
  ++_vars[dim()-1];
  for(int d = dim()-1; d > 0; --d)
  {
    if( _vars[d] >= _end[d] )
    {
      _vars[d] = _begin[d];
      ++_vars[d-1];
    }
  }
  return *this;
}
bool done()
{
  /*for(int d = 0; d < dim(); ++d)
    if( _vars[d] < _end[d] )
      return false;
  return true;*/
  return (_vars[0] >= _end[0]);
}
T operator[](int d)
{
  return _vars.at(d);
}
int numDimensions(){
  return dim();
}
std::vector<T>& getRaw(){
  return _vars;
}

};

- Adrian Park

Answer 3

如果我正确理解了你的问题，另一种方法是使用位运算符：

for(int i = 0; i < 1<<size; i++) {
    for(int j = 0; j < size; j++) {
       if(i & 1<<j) printf("%d ", a[j]);
    }
    printf("\n");
}

- Soufiane Hassou

Answer 4

你需要构建原始集合的幂集。我已经很久没有写过了，但伪代码看起来像这样：

Powerset(a, size)
{
   if(size == 0) return emptyset

   subseta = Powerset(a, size-1) // Powerset of everything except last element
   subsetb = appendToAll(a[size-1], subseta) // appends the last element to every set in subseta
   return union(subseta, subsetb)
}  

- Brian Postow

Answer 5

你很可能可以用递归来实现这个。

- Daniel A. White

---

这是对于每个问题都有效的答案。使用递归，你可以做任何事情！ - Brian Postow