비순환적 순열

#include <stdio.h>

void perm(int al[], int size) {

  int p[1000]={0,}; // stack

  int i=0, k, n, x, y, z, temp;

  p[++i]=size; // cycle back size

  p[++i]=2;    // cycle back 

  p[++i]=0;    // z 

  p[++i]=0;    // y

  p[++i]=size; // cycle size

  p[++i]=1;    // first phase

  p[0]=i;      // p[0] is TOP of stack p

  while(p[0]) { // while stack p is not empty

    k=p[p[0]--]; // phase 1 or phase 2

    n=p[p[0]--]; // remaining number of elements 

    if(k==1) {   // phase 1 : to cyle and recursive call

      y=p[p[0]--]; // exchange two elements

      z=p[p[0]--]; //

      if(y!=z) {

        temp=al[y];al[y]=al[z];al[z]=temp;

      }

      if(n==1) { // if only one elements left

        for(i=0;i<size;++i) printf("%d ",al[i]);

        printf("\n");

        continue; // finish to recursive call

      }

      for(x=0;x<n;++x) { // cycle through all the elements

        p[++p[0]]=n-1;   // cycle back to original position

        p[++p[0]]=2;     // phase 2

        p[++p[0]]=size-1-x; // exchange two elements

        p[++p[0]]=size-n;   // in reverse order

        p[++p[0]]=n-1;   // next call from this n

        p[++p[0]]=1;     // phase 1

      }

    }

    else {       // phase 2 cycle back to original positions

        temp=al[size-n];

        for(x=0;x<n;++x) al[size-n+x]=al[size-n+x+1];

        al[size-1]=temp;

    }

  }

}

int main() {

  int data[10]={1,2,3,4,5,6,7,8,9,10};

  int n;

  printf("number (from 1 to 10) : ");

  scanf("%d", &n);

  perm(data,n); 

  return 0;

}

위의 코드는 파이썬 코드에서 직역한 코드이다.

def perm(al, n, s):

    if n==1: 

        print (al)

        return

    for x in range(n):

        al[s-n],al[s-n+x]=al[s-n+x],al[s-n]

        perm(al, n-1, s)

    t=al[s-n]

    for x in range(n-1):

        al[s-n+x]=al[s-n+x+1]

    al[s-1]=t

def nperm(al, s):

    p=[]

    p.append(s)

    p.append(2)

    p.append(0)

    p.append(0)

    p.append(s)

    p.append(1)

    while p:

        k=p.pop()

        n=p.pop()

        if k==1:

            y=p.pop()

            z=p.pop()

            if y!=z: al[y],al[z]=al[z],al[y]

            if n==1: 

                print (al)

                continue

            for x in range(n):

                p.append(n-1)

                p.append(2)

                p.append(s-1-x)

                p.append(s-n)

                p.append(n-1)

                p.append(1)

        else:

            t=al[s-n]

            for x in range(n-1):

                al[s-n+x]=al[s-n+x+1]

            al[s-1]=t   

#perm([1,2,3,4], 4, 4)

nperm([1,2,3,4], 4)

        

        

위의 코드는 결코 이해하기 쉬운 코드는 아니다. 어쩌랴....