Recursive 를 이용한 Permutation Generator (순열 생성기)

기본 원리 

perm(a, b, c, d);

1) a + perm(b, c, d)

2) b + perm(a, c, d)

3) c + perm(a, b, d)

4) d + perm(a, b, c)

perm(b, c, d)

1) b + perm(c, d)

2) c + perm(b, d)

3) d + perm(b, c)

perm(c, d)

1) c + perm(d)

2) d + perm(c)

perm(a, 0, n) → a[0], a[1], ⋯, a[n-1]

소스 C++)

void Permutations (char *a, const int k, const int m) 

{// Generate all the permutations of a[k], ..., a[m].

if (k == m) {  // output permutation

for (int i = 0; i <= m; i++) cout << a[i] << “ “;

cout << endl;    

} 

else // a[k:m] has more than one permutation. Generate these recursively  

for (int i = k; i <= m; i++) {

swap(a[k], a[i]);

Permutations(a, k+1, m);

swap(a[k], a[i]);

}

}