/*
順列生成。
数列長をNとする。
N - 1桁の数の次に大きい数を探してN - 1桁と交換。
N - 1桁より後ろの数について、昇順にならべてから入れなおす。
順列1つ生成終わり。
N - 1桁の数の次に大きい数が見つからなかったら、
N - 2桁の数の次に大きい数を探してN - 2桁と交換。
N - N桁でも見つからなかったら順列生成完了。
*/
#include <stdio.h>
int nextPermutation(int num[], int length) {
int tmp, min, max;
int flag = 1;
int cnt;
int i = length - 2, j, k;
// 探索。
while( i >= 0 && flag == 1 ) {
max = 10;
cnt = 0;
for( j = length - 1; ; j-- ) {
if( num[i] < num[j] && num[j] <= max ) {
max = num[j];
tmp = j;
cnt++;
}
if( j == i ) {
if( cnt == 0 ) {
i--;
break;
} else {
flag = 0;
break;
}
}
}
}
// 生成完了。
if( i < 0 ) {
return 0;
}
// 交換。
j = tmp;
tmp = num[i]; num[i] = num[j]; num[j] = tmp;
// ソート。
if( i != length - 2 ) {
for( j = i + 1; j < length; j++ ) {
min = length - 1;
for( k = length - 1; k >= j; k-- ) {
if( num[min] > num[k] ) {
min = k;
}
}
tmp = num[j]; num[j] = num[min]; num[min] = tmp;
}
}
return 1;
}
void print(int a[], int length) {
int i;
for( i = 0; i < length; i++ ) {
printf("%d ", a[i]);
}
printf("\n");
return;
}
int main(void) {
int a[] = { 1, 2, 3, 4, 5 };
int length = sizeof(a) / sizeof(a[0]);
do {
print(a, length);
} while( nextPermutation(a, length) );
return 0;
}