c++ - 如何计算给定集合的下一个组合？

Question

• 我对原文进行了编辑，以便为潜在读者节省一些时间和健康。也许有人会真正使用它。

我知道这是基本的东西。可能非常非常基本。
如何获得给定集合的所有可能组合。例如
字符串设置 = "abc";
我希望得到:
a b c aa ab ac aaa aab aac aba abb abc aca acb acc baa bab ...
列表继续(如果没有设置长度限制)。

我正在为此寻找一个非常干净的代码 - 我发现的所有代码都有点脏而且无法正常工作。对于我编写的代码，我也可以这么说。

我需要这样的代码，因为我正在编写在多线程上工作的强力 (md5) 实现。模式是有一个父进程为线程提供它们自己的组合 block ，所以它们会自己处理这些。
示例:第一个线程获取 100 个排列组合，第二个线程获取下一个 100 个排列等等。
让我知道是否应该在任何地方发布最终程序。

编辑 #2再次感谢大家。
多亏了你，我已经完成了用 MPICH2 实现的 Slave/Master Brute-Force 应用程序(是的，可以在 linux 和 windows 下工作，例如网络)，因为这一天快结束了，我已经浪费了很多时间(和太阳)我将继续我的下一个任务......:)
您向我展示了 StackOverflow 社区非常棒 - 谢谢!

Answer 1

下面是一些 C++ 代码，可生成给定长度的幂集排列。

getPowPerms 函数接受一组字符(作为字符串 vector )和最大长度，并返回置换字符串 vector :

#include <iostream>
using std::cout;
#include <string>
using std::string;
#include <vector>
using std::vector;

vector<string> getPowPerms( const vector<string>& set, unsigned length ) {
  if( length == 0 ) return vector<string>();
  if( length == 1 ) return set;

  vector<string> substrs = getPowPerms(set,length-1);
  vector<string> result = substrs;
  for( unsigned i = 0; i < substrs.size(); ++i ) {
    for( unsigned j = 0; j < set.size(); ++j ) {
      result.push_back( set[j] + substrs[i] );
    }
  }

  return result;
}

int main() {
  const int MAX_SIZE = 3;
  string str = "abc";

  vector<string> set;     // use vector for ease-of-access            
  for( unsigned i = 0; i < str.size(); ++i ) set.push_back( str.substr(i,1) );

  vector<string> perms = getPowPerms( set, MAX_SIZE );
  for( unsigned i = 0; i < perms.size(); ++i ) cout << perms[i] << '\n';
}

运行时，这个例子打印

a b c aa ba ca ab bb cb ... acc bcc ccc

更新:我不确定这是否有用，但这里有一个名为 next 的“生成器”函数，它在给定当前列表中创建下一个项目元素。

也许您可以生成前 N 个项目并将它们发送到某个地方，然后生成接下来的 N 个项目并将它们发送到其他地方。

string next( const string& cur, const string& set ) {
  string result = cur;
  bool carry = true;
  int loc = cur.size() - 1;
  char last = *set.rbegin(), first = *set.begin();
  while( loc >= 0 && carry ) {
    if( result[loc] != last ) {             // increment              
      int found = set.find(result[loc]); 
      if( found != string::npos && found < set.size()-1 ) {
        result[loc] = set.at(found+1); 
      }
      carry = false;
    } else {                                // reset and carry        
      result[loc] = first;
    }
    --loc;
  }
  if( carry ) {                             // overflow               
    result.insert( result.begin(), first );
  }
  return result;
}

int main() {
  string set = "abc";
  string cur = "a";
  for( int i = 0; i < 20; ++i ) {
    cout << cur << '\n';        // displays a b c aa ab ac ba bb bc ...
    cur = next( cur, set );
  }
}