baileyc@boulder.Colorado.EDU (BAILEY CHRISTOPHER R) (04/08/90)
Help! I need an algorithm to generate a series of numbers. This series is of variable length. For example, if I pass a 10 to the function, it needs to generate numbers that have 10 digits. The catch is that the numbers it generates can not have more than one of the same digit, so say, the passed number is 3, it would generate the following: 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0 So, basically, there are n! number of combinations/permutations (whichever it is). Also, I would like it to start with 0 1 2 ... Right now, my function just creates all numbers by counting in the base of the number that is passed (in this case base 3), then it checks to see if there are more than one of the same digit in the number, if so it throws it out. This is being used to create node mappings for multipath graphs. My function is not good because it takes forever when you get up to >6 nodes. Thanks! Chris Bailey :: baileyc@tramp.Colorado.EDU One Agro Mountain Biker - Dialed in for ultra gonzo badness! "No his mind is not for rent, to any god or government" - RUSH Member of Team Buck Naked of Buckingham Palace
davies@sp20.csrd.uiuc.edu (James R. B. Davies) (04/10/90)
The method I use for producing permutations is pretty simple conceptually in that it is recursively structured. permute N digits: for each remaining digit save this digit permute the N-1 remaining digits end for end The following quick hack does this in C. It passes the number of digits to permuted and a bit-mask of available digits to function "permute". The current sequence being tried is kept is external variable "permutation", the total length in external variable "n_digits". When the recursion bottoms out, "report_permutation" is called to print out the result. Note that the digits are printed from n_digits-1 down to 0 so that they come out sorted the way you wanted. The main program I provided just calls permute for each number given on the command line. The initial mask should have at least as many rightmost bits set as the number of digits being permuted. Thanks for the puzzle! I enjoy this sort of thing... Jim Davies -------- cut here ------------- #include <stdio.h> char permutation[10]; int n_digits; main(argc,argv) int argc; char **argv; { while (--argc) { n_digits = atoi(*++argv); if (n_digits < 1 || n_digits > 10) exit(0); permute(n_digits, 01777); putchar('\n'); } } permute(N,mask) int N, mask; { int i, new_mask; /*printf("permute(%d,0%o)\n",N,mask);*/ for (i = 0; i < n_digits; i++) { if (mask & (1<<i)) { permutation[N-1] = '0' + i; if (N > 1) { new_mask = mask & (~ (1<<i)); permute(N-1,new_mask); } else { report_permutation(); } } } } report_permutation() { int i; for (i = n_digits-1; i >= 0; i--) { putchar(permutation[i]); } putchar('\n'); }
dfoster@jarthur.Claremont.EDU (Derek R. Foster) (04/14/90)
In article <19416@boulder.Colorado.EDU> baileyc@tramp.Colorado.EDU (BAILEY CHRISTOPHER R) writes: >Help! I need an algorithm to generate a series of numbers. This series is >of variable length. For example, if I pass a 10 to the function, it needs >to generate numbers that have 10 digits. The catch is that the numbers it >generates can not have more than one of the same digit, so say, the passed >number is 3, it would generate the following: > >0 1 2 >0 2 1 >1 0 2 >1 2 0 >2 0 1 >2 1 0 > >So, basically, there are n! number of combinations/permutations (whichever >it is). Also, I would like it to start with 0 1 2 ... This was a fun one to do. I like little challenges like this; they're a like crossword puzzles. I found a reasonably nice solution to it. It seems to work OK, although you might be able to eliminate the recursion with a little massaging. Try this: #include <stdio.h> void recurse(int *numlist, int num, int maxnum) { int i,j,norepeats; if (num >= maxnum) { for (j=0; j<maxnum; j++) printf("%d ", numlist[j]); printf("\n"); fflush(stdout); } else for (i=0; i<maxnum; i++) { for (j=0,norepeats=1; j<num && (norepeats=(numlist[j] != i)); j++); if (norepeats) { numlist[num] = i; recurse(numlist, num+1, maxnum); } } } void generatelist(int num) { int * numlist; numlist = (int *) malloc(sizeof(int) * num); recurse(numlist, 0, num); free(numlist); } void main(void) { int num; printf("Enter number?"); scanf("%d", &num); generatelist(num); } I hope this is what you wanted! Derek Riippa Foster