一、字典序法
1) 从序列P的右端开始向左扫描，直至找到第一个比其右边数字小的数字，即
。
2) 从右边找出所有比
大的数中最小的数字
，即
。
3) 交换与
。
4) 将右边的序列翻转，即可得到字典序的下一个排列。
5) 重复上面的步骤，直至得到字典序最大的排列，即左边数字比右边的大的降序排列。
//字典序法
void dictionary(int length){
int * data = (int *)malloc(sizeof(int) * length);
int index;
for (index = 0; index < length; ++index)
data[index] = index + 1;
FILE * fp = fopen("dictionary.txt", "w");
print(fp, data, length);
while (nextPermutation(data, 0, length)){
print(fp, data, length);
}
fclose(fp);
free(data);
} void swap(int data[], int i, int j){//交换两个元素
char temp;
temp = data[i];
data[i] = data[j];
data[j] = temp;
} void reverse(int data[], int first, int last){//翻转序列
last--;
while (first < last){
swap(data, first++, last--);
}
} int nextPermutation(int data[], int first, int last){
int i, j;
i = last - 2;
while (i >= 0 && data[i] >= data[i+1])
--i;
if (i == -1){
reverse(data, first, last);
return 0;
}
j = last - 1;
while (data[j] <= data[i]){
--j;
}
swap(data, i, j);
reverse(data, i + 1, last);
return 1;
} void print(FILE * fp, int data[], int length){
int index;
for (index = 0; index < length; ++index){
fprintf(fp, "%d ", data[index]);
}
fprintf(fp, "\n");
}
二、SJT Algorithm
初始状态为。
1) 找到最大的可移动数m(当一个数指向一个比它小的数是，该数就是可移动数)
2) 交换m和m所指向的数
3) 改变所有比m大的数的方向
4) 重复上面的步骤，直至找不到可移动数
//邻位对换法
void exchange(int length){
Item * data = (Item *)malloc(sizeof(Item) * length);
int index, indexOfMax;
for (index = 0; index < length; ++index){
data[index].digit = index + 1;
data[index].direction = -1;
data[index].mobile = (index != 0) ? 1 : 0;
}
indexOfMax = length - 1;
FILE * fp = fopen("exchange.txt", "w");
exPrint(data, length, fp);
while (1== data[indexOfMax].mobile || existMobile(data, length)){
if (1== data[indexOfMax].mobile){
int direction = data[indexOfMax].direction;
exSwap(data, indexOfMax, indexOfMax+direction);
indexOfMax += direction;
if ((indexOfMax == 0 && direction == -1) || (indexOfMax == length-1 && direction == 1)){
toMobileorNot(data, length);
}
} else{
index = findMax(data, length);
if (index == -1)
break;
int direction = data[index].direction;
exSwap(data, index, index + direction);
index += direction;
changeDirection(data, length, index);
toMobileorNot(data, length);
}
exPrint(data, length, fp);
}
fclose(fp);
free(data);
} int existMobile(Item data[], int length){//判断是否存在可移动数
int index;
for (index = 0; index < length; ++index){
if (data[index].mobile == 1)
return 1;
}
return 0;
} int findMax(Item data[], int length){//找到最大的可移动数
int ans = -1;
for (int index = 0; index < length; ++index){
if (data[index].mobile == 1){
if (ans == -1)
ans = index;
else if (data[index].digit > data[ans].digit)
ans = index;
}
} return ans;
} void changeDirection(Item data[], int length, int index){//改变大于可移动数的数的方向
for (int i = 0; i < length; ++i){
if (data[i].digit > data[index].digit){
data[i].direction = -data[i].direction;
}
}
} void toMobileorNot(Item data[], int length){
if (data[0].direction == 1 && data[0].digit > data[1].digit)
data[0].mobile = 1;
else
data[0].mobile = 0; for (int i = 1; i < (length - 1); ++i){
int direction = data[i].direction;
if (data[i].digit > data[i+direction].digit)
data[i].mobile = 1;
else
data[i].mobile = 0;
} if (data[length-1].direction == -1 && data[length-1].digit > data[length-2].digit)
data[length-1].mobile = 1;
else
data[length-1].mobile = 0;
} void exPrint(Item data[], int length, FILE * fp){
for (int index = 0; index < length; ++index){
fprintf(fp, "%d ", data[index].digit);
}
fprintf(fp, "\n");
} void exSwap(Item data[], int i, int j){
Item tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
三、Heap's Algorithm
procedure generate(n : integer, A : array of any):
if n = 1 then
output(A)
else
for i := 1; i ≤ n; i += 1 do
generate(n - 1, A)
if n is odd then
j ← 1
else
j ← i
swap(A[j], A[n])
以上算法描述摘自维基百科
//Recursive implementation.
#include <stdio.h>
#include <stdlib.h>
#include <time.h> FILE * fp = NULL;
int len; int str2int(char str[]){
int i = 0;
int result = 0;
while (str[i] != '\0'){
result = result * 10 + str[i] - '0';
++i;
}
return result;
} void print(int data[]){
int i;
for (i = 0; i < len; ++i)
fprintf(fp, "%d ", data[i]);
fprintf(fp, "\n");
} void swap(int *x, int *y){
int tmp = *x;
*x = *y;
*y = tmp;
} void generate(int data[], int n){
int i;
if (1 == n)
print(data);
//return;
else{
for (i = 0; i < n; ++i){
generate(data, n-1);
if (n % 2 == 1){
swap(&data[1], &data[n-1]);
} else{
swap(&data[i], &data[n-1]);
}
}
}
} void heapAlgorithm(int n){
int * data = (int *)malloc(sizeof(int) * n);
int i;
for(i = 0; i < n; ++i)
data[i] = i + 1;
generate(data, n);
free(data);
}
int main(int argc, char **argv){
fp = fopen("heap.txt", "w");
len = (argc > 1) ? str2int(argv[1]) : 10;
clock_t time = clock();
heapAlgorithm(len);
time = clock() - time;
printf("Heap's Algorithm takes %d clocks(%f seconds).\n", time, ((float)time)/CLOCKS_PER_SEC);
return 0;
}