如何计算给定集合的下一个组合的数量？

Question

• 我编辑了原始文本,以节省潜在的读者一些时间和健康.也许有人会真的使用它.

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

我正在寻找一个非常干净的代码 - 我发现的所有东西都很脏而且工作不正常.我可以说我写的代码.

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

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

Answer 1

这里有一些C++代码可以生成给定长度的功率集的排列.

该函数getPowPerms接受一组字符(作为字符串向量)和最大长度,并返回置换字符串的向量:

#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 );
  }
}

Answer 2

C++有一个函数next_permutation(),但我认为这不是你想要的.

您应该可以使用递归函数轻松完成.例如

void combinations(string s, int len, string prefix) {
  if (len<1) {
    cout << prefix << endl;
  } else {
    for (int i=0;i<s.size();i++) {
      combinations(s, len-1, prefix + s[i])
    }
  }
}

编辑:对于线程部分,我假设您正在使用密码暴力破解程序？

如果是这样,我想密码测试部分是你想要加速而不是密码生成.

因此,您可以简单地创建一个生成所有组合的父进程,然后将每个第k个密码赋予线程k mod N(其中N是线程数)以进行检查.