How to get count of next combinations for given set?

Question

• I've edited original text to save potential readers some time and health. Maybe someone will actually use this.

I know it's basic stuff. Probably like very, very basic.
How to get all possible combinations of given set. E.g.
string set = "abc";
I expect to get:
a b c aa ab ac aaa aab aac aba abb abc aca acb acc baa bab ...
and the list goes on (if no limit for length is set).

I'm looking for a very clean code for that - all that I've found was kind of dirty and not working correctly. The same I can say about code I wrote.

I need such code because I'm writing brute force (md5) implementation working on multiple threads. The pattern is that there's Parent process that feeds threads with chunks of their very own combinations, so they would work on these on their own.
Example: first thread gets package of 100 permutations, second gets next 100 etc.
Let me know if I should post the final program anywhere.

EDIT #2 Once again thank you guys.
Thanks to you I've finished my Slave/Master Brute-Force application implemented with MPICH2 (yep, can work under linux and windows across for example network) and since the day is almost over here, and I've already wasted a lot of time (and sun) I'll proceed with my next task ... :)
You shown me that StackOverflow community is awesome - thanks!

Answer 1

Here's some C++ code that generates permutations of a power set up to a given length.

The function getPowPerms takes a set of characters (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

Update: I'm not sure if this is useful, but here is a "generator" function called next that creates the next item in the list given the current item.

Perhaps you could generate the first N items and send them somewhere, then generate the next N items and send them somewhere else.

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++ has a function next_permutation(), but I don't think that's what you want.

You should be able to do it quite easily with a recursive function. e.g.

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: For the threading part, I assume you are working on a password brute forcer?

If so, I guess the password testing part is what you want to speed up rather than password generation.

Therefore, you could simply create a parent process which generates all combinations, then every kth password is given to thread k mod N (where N is the number of threads) for checking.

Answer 3

Another version of permutation is in Python's standard library although you questioned in C++.

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

But your list contains an infinitive sequence of a each character, so I think the method that how to order those should be defined first, and state your algorithm clearly.

Answer 4

I can't give you the code but what you need is a recursive algorithm here is some pseudo code

The idea is simple, concatinate each string in your set with each and every other string, then permute the strings. add all your smaller strings to your set and do the same thing again with the new set. Keep going till you are tired :)

Might be a bit confusing but think about it a little ;)

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

This will obviously cause a stack overflow because there is no terminating condition :) so put into the build_combinations function what ever condition you like (maybe size of set?) to terminate the recursion

Answer 5

Here's an odd and normally not ideal way of doing it, but hey, it works, and it doesn't use recursion :-)

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

I know you've got a perfectly good answer already (multiple ones in fact), but I was thinking a bit about this problem and I came up with a pretty neat algorithm that I might as well share.

Basically, you can do this by starting with a list of the symbols, and then appending each symbol to each other symbol to make two symbol words, and then appending each symbol to each word. That might not make much sense like that, so here's what it looks like:

Start with 'a', 'b' and 'c' as the symbols and add them to a list:

a
b
c

Append 'a', 'b' and 'c' to each word in the list. The list then looks like:

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

Then append 'a', 'b' and 'c' to each new word in the list so the list will look like this:

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

You can do this easily by using an iterator and just let the iterator keep going from the start.

This code prints out each word that is added to the list.

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

a Python example:

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

The output is exactly what you expect to get: a b c aa ab ac aaa aab aac aba abb abc aca acb acc baa bab ... (the example is using the whole ASCII lowercase chars set, change "characters = ['a','b','c']" to reduce the size of output)

Answer 8

What you want is called Permutation.

Check this for a Permutation implementation in java