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 <stdio.h>
#include <stdlib.h>
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 |
