§©®Î¶†Δ® Notes

I came across some pseudocode which promised to convert permutations to indexes and vice versa. This has been a very interesting topic to me ever since I was a 10th grader. The whole idea of calculating permutations *quickly* has consumed my rare spare brain cycles since I was given a test which asked me to solve this seemingly simple problem:

Given 3 characters, the number of possible unique combinations using each character once is 3! (three factorial), which is equal to 3x2x1, or 6 permutations. Here are the permutations in lexicographical (dictionary) order for n=3 and the characters are {A,B,C}:

1. ABC
2. ACB
3. BAC
4. BCA
5. CAB
6. CBA

--- Up to this point I was thinking "Okay, I understand that." Now imagine how it would have felt to read the actual problem: --- Write a recursive function that will return a string containing the 150,000^th permutation of the characters {A,B,C,D,E,F,G,H,I} arranged in lexicographic order.

Fortunately, this was extra credit... but I couldn't keep my mind off of the problem. Back then, there was no Internet I could go to for an answer. So, I beat myself up with this question long after the test. Anyway, back to my post... I read the pseudocode from the above link, translated it into code, and discovered that it was buggy and produced invalid permutations for a given index. So, that's where I am. In the meantime, I've found a nice and short recursive C program that writes to standard output all the permutations for a string passed in on the command line: ------------

#include <stdio.h>

char tmp,*string;

void perm(char *s){
	char *t;

	if(*s){
		perm(s+1);
		for(t=s+1;*t;t++){
			tmp=*t;
			*t=*s;
			*s=tmp;
			perm(s+1);
			tmp=*t;
			*t=*s;
			*s=tmp;
		}
	}
	else
		puts(string);
}

void main(int argc,char **argv){
	if(argc!=2){
		fprintf(stderr,"perm: Arg Error\n");
		exit(1);
	}
	perm(string=argv[1]);
}