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 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]

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]

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]

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]

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]

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]

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!

[nslay]

Code: [Select]

void permute( unsigned long *p, unsigned long sz, unsigned long n ) {
        do {
                *p ^= p[n % sz];
                p[n % sz] ^= *p;
                *p ^= p[n % sz];
        } while ( ++p, n /= sz, (--sz && n) );
}
Use XOR instead of tmp...probably would be faster to only compute n%sz once too...I trust compiler will optimize that for me.

[nslay]

turns out tmp is better since XOR fails with 0

Either way, here's an example program

Code: [Select]

#include <stdio.h>
#include <math.h>

/* Set to permute N values and display all possibilities */
#define N       6

void permute( unsigned long *p, unsigned long sz, unsigned long n );

int main( int argc, char **argv ) {
        /* Sterling's approximation */
        unsigned long x[N], i, j, s = sqrt(2*M_PI)*pow(N,N+0.5)*exp(-N+1.0/(12*N));
        for ( i = 0; i <= s; ++i ) {
                for ( j = 0; j < N; ++j ) x[j] = j+1;
                permute( x, N, i );
                printf( "%d: ", i );
                for ( j = 0; j < N; ++j ) printf( "%d ", x[j] );
                printf( "\n" );
        }

        return 0;
}

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

Sample output
N = 3

%gcc -o main -lm -ansi main.c
%./main
0: 1 2 3
1: 2 1 3
2: 3 2 1
3: 1 3 2
4: 2 3 1
5: 3 1 2
6: 1 2 3

N = 4

%gcc -o main -lm -ansi main.c
%./main
0: 1 2 3 4
1: 2 1 3 4
2: 3 2 1 4
3: 4 2 3 1
4: 1 3 2 4
5: 2 3 1 4
6: 3 1 2 4
7: 4 3 2 1
8: 1 4 3 2
9: 2 4 3 1
10: 3 4 1 2
11: 4 1 3 2
12: 1 2 4 3
13: 2 1 4 3
14: 3 2 4 1
15: 4 2 1 3
16: 1 3 4 2
17: 2 3 4 1
18: 3 1 4 2
19: 4 3 1 2
20: 1 4 2 3
21: 2 4 1 3
22: 3 4 2 1
23: 4 1 2 3
24: 1 2 3 4

[Sidoh]

Nice!  Cool stuff.  So, it turns out the recursive solution is more elegant.

[nslay]

Nice!  Cool stuff.  So, it turns out the recursive solution is more elegant.

Nah, the iterative solution is more elegant...fewer lines and more efficient

[nslay]

Guess the next challenge is to make it reentrant
That is, it would be nice to be able to call permute() consecutively to generate the next permutation

[Sidoh]

The last piece of code is the iterative solution, right?  Isn't it longer than the recursive solution you posted earlier?

[nslay]

The last piece of code is the iterative solution, right?  Isn't it longer than the recursive solution you posted earlier?

The iterative permute() function is shorter than the recursive code I posted earlier

EDIT: Yes, by one line...let me fix that

Code: [Select]

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

Regardless of lines, the iterative solution is more elegant because it is more efficient.  It will not bust the stack like the recursive solution and it does not introduce any "bloat"...it removes the "bloat" of the recursive function by not having to push itself onto the stack repeatedly.

[iago]

Of course, a slightly more elegant solution would actually implement the algorithm I asked for, not the one I mistakenly indicated in the thread's title

[nslay]

Of course, a slightly more elegant solution would actually implement the algorithm I asked for, not the one I mistakenly indicated in the thread's title

The algorithm is there, just loop and call permute() size! (which can be approximated by stirling's approximation) times on a character array.  Change the unsigned long array to a char array in permute's parameter list.
permute() takes a set of elements and arranges them based on an ordinal number, regardless of what they are, if they're repeated, etc...
"hello" is such a set of elements
so is
"Go fudge yourself iago, I'm done helping"

P.S.  If you actually intended to ask how to generate say, every possible combination of a drink, pizza topping, and crusts at a restaurant, I will hint you that it can be done synonymous to numerical base conversion.

[Chavo]

Regardless of lines, the iterative solution is more elegant because it is more efficient.  It will not bust the stack like the recursive solution and it does not introduce any "bloat"...it removes the "bloat" of the recursive function by not having to push itself onto the stack repeatedly.

!concur

Recursive solutions are almost always a bad idea if there is another way to solve a problem.  Especially if you are like me and have to worry about filling up your stack (on a microcontroller)!

[Sidoh]

I'm totally aware of the downfalls of recursion.  Efficiency and limitations have nothing to do with elegance in the context I'm referring to.

[iago]

Of course, a slightly more elegant solution would actually implement the algorithm I asked for, not the one I mistakenly indicated in the thread's title

The algorithm is there, just loop and call permute() size! (which can be approximated by stirling's approximation) times on a character array.  Change the unsigned long array to a char array in permute's parameter list.
permute() takes a set of elements and arranges them based on an ordinal number, regardless of what they are, if they're repeated, etc...
"hello" is such a set of elements
so is
"Go fudge yourself iago, I'm done helping"

P.S.  If you actually intended to ask how to generate say, every possible combination of a drink, pizza topping, and crusts at a restaurant, I will hint you that it can be done synonymous to numerical base conversion.

The thing is, the program I wanted would, for example, generate every 3-digit sequence possible using, "abcde" -- aaa aab aac aad aae aba abb abc abd abe aca acb ........

I probably explained it incorrectly in the initial post, though. My bad

[Chavo]

I'm totally aware of the downfalls of recursion.  Efficiency and limitations have nothing to do with elegance in the context I'm referring to.

I think we probably have different definitions of elegance

[Skywing]

Use XOR instead of tmp...probably would be faster to only compute n%sz once too...I trust compiler will optimize that for me.

In my experience, using temporaries is typically faster in real-world scenarios than the "XOR trick".  Regardless, it should be a small portion of the total time spent here.

[Sidoh]

I think we probably have different definitions of elegance

displaying effortless beauty and simplicity in movement or execution; "an elegant dancer"; "an elegant mathematical solution -- simple and precise"

Remember, I'm talking about the code and its mathematical meaning.  I agree that the iterative solution is more efficient and less limited, but I don't think that the code is as elegant.

If you want to continue this (I have no problem with that), I'm going to split the topic so we don't corrupt this one.

[Chavo]

I don't really care that much.

[iago]

If you want to continue this (I have no problem with that), I'm going to split the topic so we don't corrupt this one.

Corrupt all you want, I already solved the problem I needed solved, and nslay already solved the problem I asked for. So that's pretty much over, do what you will

[Sidoh]

Yes sir!