// Arup Guha
// 7/27/2020
// Solution to 2020 Summer COP 3502 Final Exam Part D Q3

#include <stdio.h>

#define N 5

// Run it for N=5.
int main(void) {
    int perm[N], used[N];
    for (int i=0; i<N; i++) used[i] = 0;
    printSpaced(perm, 0, used);
}

void printSpaced(int perm[], int k, int used[]) {

    // Base case, just print.
    if (k == N) {
        for (int i=0; i<N; i++) printf("%d ", perm[i]);
        printf("\n");
        return;
    }

    // Go through each possible choice.
    for (int i=0; i<N; i++) {

        // If it's the beginning we can do it, otherwise check if the corresponding jump is big enough.
        if (k==0 || (!used[i] && abs(i-perm[k-1])>=2)) {

            // Usual permutation code.
            used[i] = 1;
            perm[k] = i;
            printSpaced(perm, k+1, used);
            used[i] = 0;
        }
    }
}