How to get the number of the following combinations for a given set?

Question

• I edited the original text to keep potential readers some time and health. Maybe someone really uses this.

I know this basic thing. Probably very, very simple. How to get all possible combinations of a given set. E.G.
string set = "abc";
I expect to get:
abc aa ab ac aaa aab aac aba abb abc aca acb acc baa bab ...
and the list goes on (unless a length limit is specified).

I am looking for very clean code for this - everything I found was dirty and did not work correctly. The same can be said for the code I wrote.

I need this code because I'm writing brute force (md5) working on multiple threads. The pattern is that there is a parent process that feeds the threads with chunks of its own combinations, so they will work on it on their own.
Example: the first thread receives a packet of 100 permutations, the second - the next 100, etc.
Let me know if I should publish the final program anywhere.

EDIT # 2 Thanks again to you guys.
Thanks to you, I finished the Slave / Master Brute-Force application implemented using MPICH2 (yes, it can work under linux and windows, for example, over the network), and since the day is almost over, and I have already spent a lot of time (and the sun) I will continue your next challenge ... :)
You showed me that the StackOverflow community is great - thanks!

Answer 1

Here is the C ++ code that generates permutations of the power given up to the given length.

The function getPowPermsaccepts a character set (as a vector of strings) and a maximum length and returns a vector of permuted strings:

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

When run, this example prints

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

++ 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])
    }
  }
}

EDIT: , brute forcer?

, , - , , .

, , , k- k mod N ( N - ) .

Answer 3

Python, ++.

http://docs.python.org/library/itertools.html#itertools.permutations

, , , , .

Answer 4

, , , , -

, , . . , :)

, ;)

set = { "a", "b", "c"}

build_combinations(set)
{
  new_set={}
  for( Element in set ){
    new_set.add(Element);
    for( other_element in set )
      new_element = concatinate(Element, other_element);
      new_set.add(new_element);
  }

  new_set = permute_all_elements(new_set);

 return build_combinations(new_set);
}

, , - :), build_combinations , (, ?),

Answer 5

, , , : -)

void permutations(char c[], int l) // l is the length of c
{
    int length = 1;
    while (length < 5)
    {
        for (int j = 0; j < int(pow(double(l), double(length))); j++) // for each word of a particular length
        {
            for (int i = 0; i < length; i++) // for each character in a word
            {
                cout << c[(j / int(pow(double(l), double(length - i - 1))) % l)];
            }
            cout << endl;
        }
        length++;
    }
}

Answer 6

, ( ), , , .

, , , , , . , :

'a', 'b' 'c' :

a
b
c

'a', 'b' 'c' . :

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc

"a", "b" "c" , :

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abb
... and so on

, , .

, .

void permutations(string symbols)
{
    list<string> l;
    // add each symbol to the list
    for (int i = 0; i < symbols.length(); i++)
    {
        l.push_back(symbols.substr(i, 1));
        cout << symbols.substr(i, 1) << endl;
    }
    // infinite loop that looks at each word in the list
    for (list<string>::iterator it = l.begin(); it != l.end(); it++)
    {
        // append each symbol to the current word and add it to the end of the list
        for (int i = 0; i < symbols.length(); i++)
        {
            string s(*it);
            s.push_back(symbols[i]);
            l.push_back(s);
            cout << s << endl;
        }
    }
}

Answer 7

Python:

import itertools
import string

characters = string.ascii_lowercase 
max_length = 3
count = 1
while count < max_length+1:
    for current_tuple in itertools.product(characters, repeat=count):
        current_string = "".join(current_tuple)
        print current_string
    count += 1

- , : a b a a ab ac aaa aab aac aba abb abc aca acb acc baa bab... ( ASCII, "characters = ['a', 'b', 'c']", )

Answer 8

, , Permutation.

java