#include "common.h"

#define COLS 79
#define SWAP(A, i, j) { int t; t = A[i], A[i] = A[j], A[j] = t; }

#define INDENT() { for (int kk = 0; kk < depth; kk++) putchar(' '); }
        
#define PRINT_ARRAY(A, n) {                     \
        int ll;                                 \
        INDENT();                               \
        for (ll = 0; ll < n; ll++)              \
            printf("%3d ", ll);                 \
        putchar('\n');                          \
        INDENT();                               \
        for (ll = 0; ll < n; ll++)              \
            printf("%3d ", A[ll]);              \
        putchar('\n');                          \
    }

void permute(int *A, int k, int n)
{
    static int depth = 0;
    int i;

#ifdef DEBUG
    INDENT();
    printf("Permuting from k = %d till end (%d)\n", k, n);
    INDENT();
    printf("Array:\n");
    PRINT_ARRAY(A, n);
#endif

    if(k==n) {
#ifdef DEBUG
        for (i = 0; i < COLS; i++) putchar('=');
        putchar('\n');
#endif
        for (i = 0; i < n; i++) {
            printf("%d ", A[i]);
        }
        putchar('\n');
#ifdef DEBUG
        for (i = 0; i < COLS; i++) putchar('=');
        putchar('\n');
#endif
        return;
    }

#ifdef DEBUG
    INDENT();
    printf("Fix A[%d] = %d\n", k, A[k]);
#endif
    depth++;
    permute(A, k+1, n);
    depth--;

    for(i = k+1; i < n; i++){
        SWAP(A, i, k);

#ifdef DEBUG
        INDENT();
        printf("Fix A[%d] = %d\n", k, A[k]);
#endif
        depth++;
        permute(A, k+1, n);
        depth--;

        SWAP(A, k, i);
    }

    return;
}

int main(int ac, char *av[])
{
    int *array, n, i;

    if (ac != 2)
        ERR_MESG("Usage: permute n");
    if (0 > (n = atoi(av[1])))
        ERR_MESG("permute: negative argument provided");
    if (NULL == (array = Malloc(n, int)))
        ERR_MESG("permute: out of memory");
    for (i = 0; i < n; i++)
        array[i] = i+1;
    permute(array, 0, n);

    return 0;
}