Question

3) (10 pts) For the purposes of this question, a permutation of size n is any ordering of the integers 0, 1, 2, ..., n-1. We define a spaced-out permutation of size n to be a permutation such that two consecutive terms in the permutation differ by at least 2. For example, [0, 2, 4, 1, 3] is a spaced out permutation of size 5, and [5, 2, 4, 0, 3, 1] is a spaced out permutation of size 6, but [3,0, 2, 1] is not a spaced out permutation since the 2 and 1 are adjacent and differ by only 1. Fill in the blanks below so that all spaced out permutations of size N are printed out. (Note: You may use the abs function from the math library. The function takes in a single integer and returns its absolute value.) #include <stdio.h> #include <math.h> #define N 6 int main(void) { int perm[N], used[N]; for (int i=0; i<n; i++) used[i] print Spaced (perm, 0, used); return 0; = 0; void printSpaced (int perm[], int k, int used[]) { if (k N) { for (int i=0; i<n; i++) printf("%d", perm[i]); printf("\n"); return; for (int i=0; i<n; i++) { if (___ 11 )) { used[i] perm[k] printSpaced used[i] 0; سی سيه }

Answer 1

#include<stdio.h>
#include <math.h>
#define N 6
void printSpaced(int perm[], int k, int used[]);

int main(void){
   int perm[N], used[N];
   for(int i=0;i<N;i++)used[i] = 0;
   printSpaced(perm, 0, used);
   return 0;
}

void printSpaced(int perm[], int k, int used[]){
   if(k==N){
       for(int i=0;i<N;i++)printf("%d ",perm[i]);
       printf("\n");
       return ;
   }
  
   for(int i=0;i<N;i++){
       if(k==0 || (used[i]==0 && abs(perm[k-1] - i)>=2)){
           used[i] = 1;
           perm[k] = i;
           printSpaced(perm , k+1, used);
           used[i] = 0;
       }
   }
}