StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><a href="http://ideone.com/6WMWO" rel="nofollow">Click for Demo</a></p> <pre><code>#include <stdio.h> #include <stdlib.h> #define BOOL int #define TRUE (-1) #define FALSE (0) int *Generate(int n, int s1, int s2); BOOL GenerateNext(int i, int *xs, int n, int s1, int s2); void Shuffle(int *arr, int n); int main(void) { int n = 20, s1 = 2, s2 = 5; int i; int *xs = Generate(n, s1, s2); if (xs == NULL) { printf("No valid permutations.\n"); } else { printf("Permutation: [ "); for (i = 0; i < n; i++) { if (i > 0) printf(", "); printf("%d", xs[i]); } printf(" ]\n"); free(xs); } } int *Generate(int n, int s1, int s2) { int *xs = (int *) malloc(sizeof(int) * n); if (GenerateNext(0, xs, n, s1, s2)) { return xs; } free(xs); return NULL; } BOOL GenerateNext(int i, int *xs, int n, int s1, int s2) { int candidates[n]; int nCandidates = 0, candidate, j, delta; BOOL ok; if (i == n) return TRUE; for (candidate = 0; candidate < n; candidate++) { ok = TRUE; for (j = 0; j < i && ok; j++) { if (xs[j] == candidate) ok = FALSE; else if ((i - j) <= s1) { int delta = xs[j] - candidate; if (delta < 0) delta = -delta; if (delta <= s2) ok = FALSE; } } if (ok) { candidates[nCandidates++] = candidate; } } if (nCandidates == 0) return FALSE; Shuffle(candidates, nCandidates); for (j = 0; j < nCandidates; j++) { xs[i] = candidates[j]; if (GenerateNext(i + 1, xs, n, s1, s2)) { return TRUE; } } return FALSE; } void Shuffle(int *arr, int n) { int i, j, tmp; for (i = 0; i < n; i++) { j = i + rand() % (n - i); if (j != i) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } } </code></pre> <p><strong>Edit:</strong> Rewrote the answer to be able to determine if there are any valid permutations.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload