#include <stdio.h>
#define N 10

void perm_non_pm(int start, int n, int x[])
{
  int i;
  int y[N];
  for (i=0; i<N; i++) y[i]=x[i];
  if (start == n) {
    for (i=0; i<n; i++) 
      printf("%d",y[i]);
    printf("\n");
    return;
  }
  for (i=0; i<n-start; i++) {
    int temporary;
    /* y[start]とy[start + i]を入れ替える*/
    temporary = y[start];
    y[start] = y[start + i];
    y[start + i] = temporary;
    /* もし その結果、隣合う数の差が1ならその先探さない*/
    if ((start == 0) 
        || ((y[start-1]-y[start]!=1) 
	    && (y[start-1]-y[start]!=-1)))
      perm_non_pm(start+1, n, y);
  }
  return;
}

main(void)
{
  int i, n, x[N];
  printf("隣り合う数が2以上離れているようなn個の元の置換を全て求めます。\n");
  printf("nを入力ください。\n");
  printf(" n=");
  scanf("%d",&n);
  for (i=0;i<n;i++) x[i]=i;
  perm_non_pm(0,n,x);
}