Projects/LinearPermutations

This is a simple C implementation of a short algorithm I wrote (I am not claiming to be the first), which discovers all unique permutations of a number of items.

Example

If you were to run this with the parameter '3', it would print:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Note that you are entering the n value for this algorithm, which runs in O(!T) time, where T is the output factor.

What is this?

It is simply a perversion of something everyone does recursively (for good reason), that I felt personally obliged to write iteratively.

Why?

God knows. Maybe.

Could it be improved upon?

Yes. This code is terrible.

(This page has been locked for your protection.)

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * This program uses the principal of variable length
 * and distance shifting over a set of given items, in
 * order to create all possible permutations of that
 * unique set in linear space, and linear output-based time
 * complexity O(T).
 */

unsigned int max;

void print(unsigned int *list, unsigned int len) {
        int i;
        for(i=0; i < len; i++) {
                printf("%i ", list[i]);
        }
        printf("\n");
}

int main (int argc, char **argv) {
        unsigned int *list;
        unsigned int *states;
        unsigned int *temp;          // used for swapping
        unsigned int i = 0, j, k;
        if(argc > 1) max = atoi(argv[1]);
        else max = 4;

        list = (unsigned int*)malloc(sizeof(unsigned int)*max);
        // memory is less valued than speed; use a few spots up.
        states = (unsigned int*)malloc((sizeof(unsigned int)+1)*max);
        temp = (unsigned int*)malloc(sizeof(unsigned int)*max);

        while(i < max) list[i]=++i;
        for(i=0;i <= max;i++) states[i]=0;

        print(list,max);

        for(;;) {

                // do shift on 2 of 1
                //printf("SHIFT %i by %i STATIC\n",2,1);
                i=list[max-1];
                list[max-1] = list[max-2];
                list[max-2] = i;
                print(list,max);

                // finds next state that needs to be updated
                // ie. next length to push.
                for(i=3; states[i] == i - 1; i++);
                if(i == max+1) break;

                states[i]++;
                //printf("SHIFT %i by %i\n",i,states[i]);

                j = states[i];
                memcpy(temp, list+max-j, sizeof(unsigned int)*j);

                for(k = max-1; k >= max-i+j; k--)
                        list[k] = list[k-j];

                memcpy(list+max-i, temp, sizeof(unsigned int)*j);

                print(list,max);

                for(i-=1; i >= 3; i--) states[i] = 0;

        }
}

To download this source, click here: Upload:permutations.c