/*% cc -O3 -o # %
* permut N
* Compute permutations of N objects.
* It uses an elementary algorithm to
* enumerate all N! possible permutations.
* Every integer between 0 and N!-1 is
* decomposed as a sequence
* a_{n-1} + (n-1)*(a_{n-2} + (n-2)*(... 1*a_1) ... )
* where 0 <= a_k < k. Then each a_k is
* used to swap the current permutation.
*
* Note that each permutation of N
* elements can be viewed as a the
* identity permutation where the first
* element has been swapped with one of
* the N-1 following elements, the second
* with one of the N-2 following, etc.
*/
#include
#include
#define N 30
unsigned
fact(unsigned n)
{
unsigned f=1;
for (; n; n--)
f*=n;
return f;
}
#define swap(a,b,t) t=a, a=b, b=t
int
main(int argc, char **argv)
{
unsigned n, f, i, j, x, t;
int a[N];
if (argc<2 || !(n=strtol(argv[1], 0, 0)) || n>N) {
fputs("usage: permut N\n", stderr);
exit(1);
}
f=fact(n);
for (i=0; i