CODEWITHSUNDEEP
calgorithmcombinatorics
Hans Mueller
Hans Mueller

Reputation: 11

All Possible combinations in C

I'm trying to find a efficient algorithm in C, which provides me all combinations of a given charset.

The algorithm should not recursive. At last the number of digits should be flexible. For example:

char set[] = "a1";
->
a1
aa
1a
11

I've only found a Perl solution, but it uses substr(). I think that wasn't that fast performance-wise.

For most algorithms in C, I've found were only permutations...

A article in a german C++ forum claims, that C++-STL Solutions are faster than "raw" recursive algorithms.

Upvotes: 1

Views: 5726

Answers (5)

dawg
dawg

Reputation: 103694

Python is very close to a pseudo code.

You can read the Python source to itertools.permutations and just replicate in C.

Here is the demo that this works:

#!/usr/bin/env python
import itertools

s='a1'

print set(itertools.permutations(s*len(s), len(s)))

Output:

set([('1', '1'), ('a', '1'), ('a', 'a'), ('1', 'a')])

Here is an even simpler way:

>>> s='a1'
>>> ['{}{}'.format(x,y) for x in s for y in s]
['aa', 'a1', '1a', '11']


>>> s='abc'
>>> ['{}{}{}'.format(x,y,z) for x in s for y in s for z in s]
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 
 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 
 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 
 'cca', 'ccb', 'ccc']

To unwind a list comprehension, use NESTED LOOPS, like so:

>>> for x in s:
...    for y in s:
...       for z in s:
...          print '{}{}{}'.format(x,y,z)

Upvotes: 2

jtniehof
jtniehof

Reputation: 601

Wikipedia has C code for the n-ary Gray code. It should be convertible to your problem by using the digits as offsets into your input array. You will need to do some dynamic allocation to handle the arbitrary length of your input. A related approach is to do nested loops, where you have an array of loop counters as long as your input, and another counter for which of those you are currently incrementing. E.g. printing all six-digit base-six numbers, needs to be modified for dynamic allocation but shows the principle:

int i;
int length = 5;
int max = 6;
int counters[length];
for (i=0; i<length; i++)
    counters[i] = 0;
for(;;) {
    for (i=length-1; i>=0; i--)
        printf("%d", counters[i]);
    printf("\n");
    for(i=0; i<length; i++) {
        counters[i]++;
        if (counters[i] < max)
            break;
        else
            counters[i] = 0;
    }
    if (i >= length)
        break;
}

Upvotes: 2

Tom Cerul
Tom Cerul

Reputation: 1943

Write a function that will convert an integer into a string hexadecimal number, then convert that algorithm into a base 36 (a-z plus 0-9) number. Use one for loop to count from 1 to (digit count times base) and call your function each time.

  • 1 becomes 1
  • 10 becomes a
  • 35 becomes z
  • 36 becomes 10
  • 46 becomes 1a

Upvotes: 0

pmg
pmg

Reputation: 108968

Well, I would number the possible combinations, loop through the numbers and convert.

For instance: to generate all size 3 combinations of the 10 symbols {'0', '1', ..., '9'}, I would loop from 0 to 999 and output "000" to "999".

In the same way (kinda), to generate all size 3 combinations of the 5 symbols {'a', 'b', ..., 'e'} I would loop from 0 to 5*5*5-1 and output the loop number in base 5, but with the symbols provided.

Upvotes: 0

Robin Green
Robin Green

Reputation: 33033

If the set size were a fixed N it would be simple - you could just have N for loops, each one nested into the previous one. Since you can't do this and you can't use recursion, you have to calculate the total required number of iterations (seems like it's N^M), use one single loop and then use / and % to calculate what the array index of each character should be. You'd better use longs as well, because N^M gets big fast.

Upvotes: 2

Related Questions