View Question
 Question
 Subject: Numeric Permutations Category: Science > Math Asked by: da_maury-ga List Price: \$5.00 Posted: 01 Nov 2002 13:51 PST Expires: 01 Dec 2002 13:51 PST Question ID: 95825
 ```Given a sequence from 1 to 8, what formula will calculate each unique combination using all 8 values. I believe there are 256 unique sequences. For example: Seq 1) 1,2,3,4,5,6,7,8 Seq 2) 2,1,3,4,5,6,7,8 Although I can do this by hand, it is not efficient. The correct answer should be adaptable to a computer routine, preferably in C++ or VB.``` Clarification of Question by da_maury-ga on 01 Nov 2002 14:12 PST ```I do not want the individual values re-used in a given sequence (therefore, the sequence 1,1,2,3,4,5,6,7 is invalid.) Each sequence must use all values once and only once. Thanks!```
 Subject: Re: Numeric Permutations Answered By: till-ga on 01 Nov 2002 14:45 PST Rated:
 ```First of all the definition for your problem: "Permutation A permutation is a way to order a set of things. For example, if your set is the letters in the word WHO, then one other ordering would be WOH. Here are all the possible orderings of the letters in the word WHO: WHO WOH HWO HOW OWH OHW There are 6 different ways to order the letters in the word WHO. ... How about the word "STOP"? Well, here they are: STOP STPO SOTP SOPT SPTO SPOT <- starts with "S" TSOP TSPO TOSP TOPS TPSO TPOS <- starts with "T" OSTP OSPT OTSP OTPS OPST OPTS <- starts with "O" PSTO PSOT PTSO PTOS POST POTS <- starts with "P" There are 24 ways to order the letters in "STOP". Is there a general rule here? Fortunately, yes. Here's the rule for "STOP": There are 4 ways to pick the first letter. After you pick the first letter there are 3 ways to pick the second letter. After you pick the first 2 letters, there are 2 ways to pick the third letter. After picking the first 3 letters, there is only 1 letter left to pick. So the number of ways to order the letters in "STOP" is 4 x 3 x 2 x 1 = 24 ways!" from: ( http://www.blarg.net/~math/def.cgi?t=permutation ) So your first guess of 256 is wrong. The rule applied to your problem is: The number of permutations of your sequence of eight numbers is: 8!=1x2x3x4x5xy6x7x8 8! = 40.230 The following c routine will output all combinations as desired: "/*===================================================================*/ /* C program for distribution from the Combinatorial Object Server. */ /* Generate permutations in lexicographic order. This is */ /* the same version used in the book "Combinatorial Generation" by */ /* Frank Ruskey. */ /* The program can be modified, translated to other languages, etc., */ /* so long as proper acknowledgement is given (author and source). */ /* Programmer: Frank Ruskey 19??, Joe Sawada, 1997. */ /* The latest version of this program may be found at the site */ /* http://www.theory.uvic.ca/~cos/inf/perm/PermInfo.html */ /*===================================================================*/ /******************************************************************** * Modified to print permutation to file. * may 1st, 2002 by edmond ********************************************************************/ //predirective #include #include int n; int a[100]; /* The permutation */ char filename[30]; FILE *infile; void PrintPerm() { int i; for (i=1; i <= n; i++){ fprintf( infile, "%d ", a[i] ); printf ( "%d ", a[i]); } fprintf(infile, "\n"); printf ("\n"); } void swap(int i, int j) { int temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } int Next() { int k,j,r,s; k = n-1; while (a[k] > a[k+1]) k--; if (k == 0) return(0); else { j = n; while (a[k] > a[j]) j--; swap(j,k); r = n; s = k+1; while (r>s) { swap(r,s); r--; s++; } } PrintPerm(); return(1); } int main () { int i; printf( "Enter n: " ); scanf( "%d", &n ); if (n<=0) exit(1); printf ( "Enter filename: " ); scanf( " %s", filename); infile = fopen( filename, "w"); if( !infile ){ printf("Error opening file to write\n"); return 0; } printf( "\n" ); for (i=0; i<=n; ++i) { a[i] = i; } PrintPerm(); while (Next()); printf( "\n" ); fclose(infile); printf("Press Enter to Continue..."); fflush( stdin ); getchar(); getchar(); return 0; } " from: ( http://www.maximalgorithms.com/algorithms.html ) Search Strategy: ( ://www.google.de/search?sourceid=navclient&hl=de&q=permutation+definition ) and ( ://www.google.de/search?sourceid=navclient&hl=de&q=permutation+c+numbers ) till-ga```
 da_maury-ga rated this answer: ```Excellent and thorough response! By the way, thank you to both researchers for the correction to my underestimate. I'll be back with more!```

 ```Just as a note to any researcher who attempts this question, after a couple of minutes thinking about a possible solution, I think there's actually 8!=40320 possible permutations.```
 ```I just want to point out that the calculation of 8!=40230 is not correct in the researchers response, and is correct(8!=40320) in the previous comment. Probably just a typo.```
 ```Thank you kdb003-ga for your hint at my typo. Of course you are right: 8!=40.320. Sorry for that da_maury-ga and thanks for still giving the high rating. till-ga```