编写一个程序,用字典顺序列出n个元素的所有排列(Permutation)

说明:
下面是一个n = 4，用字典顺序列出来的所有排列，一共为4! = 24个。

1234 2134 3124 4123

1243 2143 3142 4132

1324 2314 3214 4213

1342 2341 3241 4231

1423 2413 3412 4312

1432 2431 3421 4321

字典顺序的先后是这样定义的, 如果a(1)a(2)…a(n)与b(1)b(2)…b(n)是n个元素的两个排列于是有a(1)=b(1), a(2)=b(2),…a(i)=b(i),但a(i+1)<b(i+1), 就是说a(1)a(2)a(n)。在b(1)b(2)b(n)的前面,或者说前者较”小”; 注意,自i+2个之后的各个元素是没有影响的。其实, 这就是用来决定字符串大小的方式。举例而言, 2314与2341,前两个元素相同,但第三个为1<4,所以2314在前, 2341在后; 同理, 1234与4321相比, 1234在前,4321在后。

如何产生字典顺序的排列呢? 据Hall与 Knuth的考证, 200年(1812年)前Fischer与Kruse在他们的一本书中就已经提过这样的方法了。从1234…n开始,首先从右到左出第一对满足a(i)<a(i+1)的a(i)与a(i+1),于是从a(i+1)起在它右边的就是越来越小的:有了a(i)之后再一次地从右到左查一次,找出第一个满足a(i)< a(j)的a(j)。接着把a(i+1)到a(n)的各个元素反过来排, 就是字典顺序的下一个了。下面来看看如何找出153642的下一个:从右到左第一组满足a(i) < a(i+1)的是3与6,所以a(i),就是3。接着从右到左去找第一个a(j),使得a(i) < a(j),则是3 < 4; 最后把3与4之间的元素反过来排,因此得到154632,这就是结果。

看另一个递归的做法。看上面4! = 24个排列的第一列，它们的第一个元素都是1，第一列的最后一个是以1开头，用字典顺序排出来的最后，自然是1432.事实上，如果是n个元素的排列，以1开头的最后一个应该是1n(n-1)…432。下一列是2开头，把n(n-1)…432中最小的一个与第一个互换，也就是把倒数第一个与第一个互换，得到2n(n-1)..431，但这不是1n(n-1)…432的下一个，但是如果把后面的n - 1个元素反过来，就会得到2134…(n-1)n，是正确的顺序，于是进入第二列。

第二列的最后一个应该是2n(n-1)…431,把 n(n-1)…431中最小的与第一个互换，但因为1已经出现过了，所以把倒数第二个元素(自然是3)与第一个互换，得到3n(n-1)…421，再把后面的n - 1个元素反过来，得到3124…(n-1)n，就得到第三列的第一个。

第三列的最后一个是3n(n-1)…421, 把n(n-1)…421中最小的与第一个互换，但因为1，2已经出现过了，所以把倒数第3个元素(自然是4)与第一个互换，得到4n(n-1)…321，再将后面n - 1个反过来排，得到4123…(n - 1)n，正好是第4列的第一个元素。

于是我们可以得到一个递归的做法，从1234…n起，用一个递归的程序

1. i = n
2. 对后面n - 1个进行排列(递归的)
3. 把第i位与第1位互换
4. i减去1
5. 把后面的n - 1位反过来排
6. 回到第2步

当i到第一位时程序结束。

解答见recursion_permutation.py