文章目錄

C语言名题精选百则之产生所有排列字典顺序递归解说过,产生所有排列还有非递归解。

如何产生字典顺序的排列呢? 据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; 把a(i)和a(j)换下位置,最后把a(i+1)与a(n)之间的元素反过来排,因此得到154236,这就是结果。

  1. i = n - 1
  2. 从右往左找,找到第一个i使得a(i) < a(i+1)
  3. 从右往左找,找到第一个j使得a(i) < a(j)
  4. 交换a(i)与a(j)
  5. 将a(i+1),…a(n)反转
  6. 回到第2步

如果找不到满足条件的i, 则结束程序。

例如153642, 从右往左找,找到第一个 i = 2 使得a(i) < a(i+1) 即3 < 6, 从右往左找,找到第一个 j = 3 使得a(i) < a(j) 即 3 < 4 交换a(i)和(j), 得到154632, 将a(i+1),..a(n)反转,即将632反转,得到154236, 所以154236就是153642的下一个排列。

解答见iteration_permutation.py

文章目錄