fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define BOOL int
  5. #define TRUE (-1)
  6. #define FALSE (0)
  7.  
  8. int *Generate(int n, int s1, int s2);
  9. BOOL GenerateNext(int i, int *xs, int n, int s1, int s2);
  10. void Shuffle(int *arr, int n);
  11.  
  12. int main(void)
  13. {
  14.     int n = 20, s1 = 2, s2 = 5;
  15.     int i;
  16.     int *xs = Generate(n, s1, s2);
  17.     if (xs == NULL)
  18.     {
  19.         printf("No valid permutations.\n");
  20.     }
  21.     else
  22.     {
  23.         printf("Permutation: [ ");
  24.         for (i = 0; i < n; i++)
  25.         {
  26.             if (i > 0) printf(", ");
  27.             printf("%d", xs[i]);
  28.         }
  29.         printf(" ]\n");
  30.  
  31.         free(xs);
  32.     }
  33. }
  34.  
  35. int *Generate(int n, int s1, int s2)
  36. {
  37.     int *xs = (int *) malloc(sizeof(int) * n);
  38.     if (GenerateNext(0, xs, n, s1, s2))
  39.     {
  40.         return xs;
  41.     }
  42.     free(xs);
  43.     return NULL;
  44. }
  45.  
  46. BOOL GenerateNext(int i, int *xs, int n, int s1, int s2)
  47. {
  48.     int candidates[n];
  49.     int nCandidates = 0, candidate, j, delta;
  50.     BOOL ok;
  51.  
  52.     if (i == n) return TRUE;
  53.  
  54.     for (candidate = 0; candidate < n; candidate++)
  55.     {
  56.         ok = TRUE;
  57.         for (j = 0; j < i && ok; j++)
  58.         {
  59.             if (xs[j] == candidate) ok = FALSE;
  60.             else if ((i - j) <= s1)
  61.             {
  62.                 int delta = xs[j] - candidate;
  63.                 if (delta < 0) delta = -delta;
  64.                 if (delta <= s2) ok = FALSE;
  65.             }
  66.         }
  67.         if (ok)
  68.         {
  69.             candidates[nCandidates++] = candidate;
  70.         }
  71.     }
  72.  
  73.     if (nCandidates == 0) return FALSE;
  74.  
  75.     Shuffle(candidates, nCandidates);
  76.  
  77.     for (j = 0; j < nCandidates; j++)
  78.     {
  79.         xs[i] = candidates[j];
  80.         if (GenerateNext(i + 1, xs, n, s1, s2))
  81.         {
  82.             return TRUE;
  83.         }
  84.     }
  85.  
  86.     return FALSE;
  87. }
  88.  
  89. void Shuffle(int *arr, int n)
  90. {
  91.     int i, j, tmp;
  92.     for (i = 0; i < n; i++)
  93.     {
  94.         j = i + rand() % (n - i);
  95.         if (j != i)
  96.         {
  97.             tmp = arr[i];
  98.             arr[i] = arr[j];
  99.             arr[j] = tmp;
  100.         }
  101.     }
  102. }
  103.  
Success #stdin #stdout 0.03s 1808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Permutation: [ 3, 19, 13, 7, 0, 14, 8, 2, 15, 9, 1, 16, 10, 4, 17, 11, 5, 18, 12, 6 ]
https://ideone.com/6WMWO
language:
C (gcc 8.3)
created:
13 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!