Generating combinations (permutations?)

[nslay]

Code Select Expand

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 Expand

#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 Expand

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 :P

[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 :P

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 :P

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.