Author Topic: Generating combinations (permutations?)  (Read 11458 times)

0 Members and 1 Guest are viewing this topic.

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: Generating combinations (permutations?)
« Reply #15 on: May 11, 2007, 03:00:42 am »
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.
An adorable giant isopod!

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: Generating combinations (permutations?)
« Reply #16 on: May 11, 2007, 03:39:18 am »
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
Quote
%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
Quote
%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


An adorable giant isopod!

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Generating combinations (permutations?)
« Reply #17 on: May 11, 2007, 03:45:31 am »
Nice!  Cool stuff.  So, it turns out the recursive solution is more elegant.

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: Generating combinations (permutations?)
« Reply #18 on: May 11, 2007, 03:49:11 am »
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 :)
An adorable giant isopod!

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: Generating combinations (permutations?)
« Reply #19 on: May 11, 2007, 04:08:04 am »
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
An adorable giant isopod!

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Generating combinations (permutations?)
« Reply #20 on: May 11, 2007, 04:17:26 am »
The last piece of code is the iterative solution, right?  Isn't it longer than the recursive solution you posted earlier?

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: Generating combinations (permutations?)
« Reply #21 on: May 11, 2007, 04:19:22 am »
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.
« Last Edit: May 11, 2007, 04:26:15 am by nslay »
An adorable giant isopod!

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: Generating combinations (permutations?)
« Reply #22 on: May 11, 2007, 10:20:54 am »
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

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: Generating combinations (permutations?)
« Reply #23 on: May 11, 2007, 10:46:00 am »
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.


« Last Edit: May 11, 2007, 10:51:11 am by nslay »
An adorable giant isopod!

Offline Chavo

  • x86
  • Hero Member
  • *****
  • Posts: 2219
  • no u
    • View Profile
    • Chavoland
Re: Generating combinations (permutations?)
« Reply #24 on: May 11, 2007, 10:46:11 am »
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)!

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Generating combinations (permutations?)
« Reply #25 on: May 11, 2007, 10:58:43 am »
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. :-\

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: Generating combinations (permutations?)
« Reply #26 on: May 11, 2007, 11:04:33 am »
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 :)

Offline Chavo

  • x86
  • Hero Member
  • *****
  • Posts: 2219
  • no u
    • View Profile
    • Chavoland
Re: Generating combinations (permutations?)
« Reply #27 on: May 11, 2007, 11:08:34 am »
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 :)

Offline Skywing

  • Full Member
  • ***
  • Posts: 139
    • View Profile
    • Nynaeve
Re: Generating combinations (permutations?)
« Reply #28 on: May 11, 2007, 11:10:34 am »
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.

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Generating combinations (permutations?)
« Reply #29 on: May 11, 2007, 12:34:51 pm »
I think we probably have different definitions of elegance :)

Quote
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.