Generating combinations (permutations?)

[iago]

Let's say I have an array of characters, and I want to build every possible X digit string. Does anybody know how the algorithm would work?

If I had a constant length string, like 3 characters, it would be easy:
for(j = 0; j < size; j++)
  for(k = 0; k < size; k++)
    for(l = 0; l < size; l++)
      str = choices[j] + choices[k] + choices[l];

But I can't think of how to extend that to any length, easily.

An idea or implementation in any language would be helpful, since I have to implement this in more than one language anyways.

[iago]

Nevermind, I got it working, basically.

- Take an array of the proper length. Set it to {0, 0, 0, ....}
- Pick the character at the index of each element in the array. Initially, it'll be 0th, 0th..., 0th. Then it'll be 0th, 0th.. 1st, etc.
- Increment the last character
- Check if it's over the size of possible characters; if so, go left and repeat; when the left-most one overflows, we're done.

That's pretty much how it works. I've tested it, and it does generate every possible combination.

[Sidoh]

It would seem to me that a recursive implementation is a more elegant approach to this problem.  However, maybe it doesn't work properly for this problem.

[iago]

As a rule of thumb, I try to avoid recursion whenever possible. It's slow, and typically iterative algorithms are better.

[Sidoh]

Yes, I know, but recursion is more mathematically beautiful.  I said elegant, not efficient. ;)

Of course, I don't really care how you implement it.  I was just wondering if you'd considered it. :)

[iago]

Haha. Yes, I considered it. But I wanted to keep it simple and fast since it'll be running a lot.

[Ender]

Here's a solution, but not the solution you're looking for, and by that I mean the most theoretically efficient algorithm. I was hoping this could help lead to the the solution. I have to go to sleep right now... so I can't work on it anymore ;-\

Oh, and yeah, it's recursive.

Given an array of characters of size n (a stringbuffer of length n), it adds every permutation nPn to a HashSet. The HashSet is O(1) in searching for elements and all non-unique entries are overriden. I then substring each length-n permutation to length x, the number of digits you desire. This will get all permutations of length x from the array of size n.

I haven't really checked it over that much but I did check it on my calculator :P In my case, n = 8 and r = 4. Thus nPr = 8 * 7 * 6 * 5 = 1680. The last line printed out confirms that the HashSet has a size of 1680 keys.

Code Select Expand


import java.util.*;

public class DynamicPermutation {

private static HashSet<String> perms = new HashSet<String>();

private static void swap(StringBuffer str, int i, int j) {
char c1 = str.charAt(i);
char c2 = str.charAt(j);
str.setCharAt(i, c2);
str.setCharAt(j, c1);
}

public static void permutations(StringBuffer str, int n, int const_numDigits) {
if (n <= 1) {
String perm = str.substring(0, const_numDigits);
perms.add(perm);
}
else {
for (int i = 0; i < n; i++) {
swap(str, i, n-1);
permutations(str, n-1, const_numDigits);
swap(str, n-1, i);
}
}
}

public static void main(String[] args) {
StringBuffer str = new StringBuffer("abcdefgh");
permutations(str, 8, 4);
for (String s : perms) {
System.out.println(s);
}
System.out.println(perms.size());
}

}


[nslay]

Code Select Expand

void permute( unsigned long *p, unsigned long sz, unsigned long n ) {
        unsigned long tmp;
        if ( !sz ) return;
        /* Swap chosen element with first element */
        tmp = p[0];
        p[0] = p[n % sz];
        p[n % sz] = tmp;
        /* Call the permute() again, noting that p[0] is now excluded so it will
not be chosen again */
        permute( p+1, sz-1, n/sz );
}

Had to do this with latin hypercube sampling and came up with this

[Sidoh]

Code Select Expand

void permute( unsigned long *p, unsigned long sz, unsigned long n ) {
        unsigned long tmp;
        if ( !sz ) return;
        /* Swap chosen element with first element */
        tmp = p[0];
        p[0] = p[n % sz];
        p[n % sz] = tmp;
        /* Call the permute() again, noting that p[0] is now excluded so it will
not be chosen again */
        permute( p+1, sz-1, n/sz );
}

Had to do this with latin hypercube sampling and came up with this

Elegant!

[nslay]

Code Select Expand

void permute( unsigned long *p, unsigned long sz, unsigned long n ) {
        unsigned long tmp;
        if ( !sz ) return;
        /* Swap chosen element with first element */
        tmp = p[0];
        p[0] = p[n % sz];
        p[n % sz] = tmp;
        /* Call the permute() again, noting that p[0] is now excluded so it will
not be chosen again */
        permute( p+1, sz-1, n/sz );
}

Had to do this with latin hypercube sampling and came up with this

Elegant!

Would be more elegant if it were an iterative solution :'(

[Sidoh]

But that'd make the code heavier and bulkier, thereby making it less elegant by definition, yes?

[nslay]

But that'd make the code heavier and bulkier, thereby making it less elegant by definition, yes?

No, the recursive solution can bust the stack for a sufficiently large data set

[Sidoh]

Yes, I know.

However, isn't that an issue of efficiency and limitation?  I'm referring to the mathematical elegance of the code, not its performance.

[nslay]

Code Select Expand

void permute( unsigned long *p, unsigned long sz, unsigned long n ) {
        unsigned long tmp;
        /* Swap chosen element with first element */
        tmp = p[0];
        p[0] = p[n % sz];
        p[n % sz] = tmp;
        /* Call the permute() again, noting that p[0] is now excluded so it will
not be chosen again */
        permute( p+1, sz-1, n/sz );
}

Had to do this with latin hypercube sampling and came up with this

Try this out, I think it should be equivalent

Code Select Expand

void permute( unsigned long *p, unsigned long sz, unsigned long n ) {
        unsigned long tmp;
        do {
                tmp = p[0];
                p[0] = p[n % sz];
                p[n % sz] = tmp;
        } while ( ++p, n /= sz, --sz );
}


[Sidoh]

Cool!