Fischer-Krause ordered
Here's a little program that generates all permutations of all the words
on each line of input. The algorithm embodied in the "permute()"
function is discussed in Volume 4 (still unpublished) of Knuth's *The
Art of Computer Programming* and will work on any list:
#!/usr/bin/perl -n
# Fischer-Krause ordered permutation generator
sub permute (&@) {
my $code = shift;
my @idx = 0..$#_;
while ( $code->(@_[@idx]) ) {
my $p = $#idx;
--$p while $idx[$p-1] > $idx[$p];
my $q = $p or return;
push @idx, reverse splice @idx, $p;
++$q while $idx[$p-1] > $idx[$q];
@idx[$p-1,$q]=@idx[$q,$p-1];
}
}
permute { print "@_\n" } split;
来自 perldoc -q permute, 调用示例:echo a b c | permute.pl
解读和代码转C,主要是有一个数字调换的规律
/* Translate by 523066680@163.com */
#include <stdio.h>
void splice_and_reverse( int *arr, int p, int ubound )
{
int t;
for (int i = p; i <= (ubound+p)/2 ; i++ )
{
t = arr[i];
arr[i] = arr[ubound - i + p];
arr[ubound - i + p] = t;
}
}
void exchange(int *arr, int a, int b)
{
int t;
t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
void print_array(int *arr, int ubound)
{
for (int i = 0; i <= ubound; i++)
printf("%d", arr[i]);
printf("\n");
}
int main(int argc, char *argv[] )
{
int arr[] = {0, 1, 2, 3};
int ubound = sizeof(arr) / sizeof(arr[0]) - 1;
int p, q;
while (1)
{
p = ubound;
//p 递减,直到 当前元素 > 上一个元素 ,上一个元素记为 N
while ( arr[p-1] > arr[p] ) p--;
if ( p <= 0 ) break;
q = p;
//反转 从 p 至 末尾的元素
splice_and_reverse( arr, p, ubound );
//q 递增,直到当前元素 > N
while ( arr[p-1] > arr[q] ) q++;
//交换
exchange(arr, p-1, q);
//打印结果
print_array(arr, ubound);
}
return 0;
}
有了这一个规则,我们可以 通过某个中间的排列得出下一个结果:
举一个 6 位的
arr[] = 5 3 4 2 1 0
- 从右往左寻找 前一项小于当前项 的情况(3和4), 下标 p = 2; 记住前一项 = 3
- 反转以 p 为起点,至末尾的项, arr[] = 5 3 0 1 2 4
- 之后的计算依据 5 3 0 1 2 4
- 以 arr[2] 为起点,向右寻找 > 3 的项的下标, 4 > 3, 所以 q = 5;
从 5 3 0 1 2 4 调换 arr[p-1], arr[q], 得
arr[] = 5 4 0 1 2 3
等有时间就做个图什么的... 未完待续