一直以来我对数的排列这类算法问题都感到很头痛，曾经囫囵吞枣看过一些算法，可是浅尝辄止，没有实际操作所以每次都忘记。上周三算法分析与设计课的内容是递归，老师正好提到了排列数这一问题，于是就有机会稍微进行一些研究。

一个排列（permutation）就是对一组对象或者数值按照某种特定的方式进行排列组织（ar-rangement），为了方便起见我们以一个数集{1, 2, 3}为例，它的全排列共有3!=6种，即{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}，上述列举排列的顺序又称为按字典序列举排列，具体将在下文进行叙述。

一、字典序

在Wikipedia中，字典序的解释是这样的：

In mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order  or lexicographic(al) product), is a natural order  structure of the Cartesian product of two ordered sets.

如果你拥有一个字典，那么里面所有的字符串都是按照字典序来进行排序的，假设有两个字符串：

a₁, a₂, …, a_n

以及

b₁, b₂, …, b_n

若存在一个m>0，使得对于所有的i<m有a_i=b_i，并且a_m<b_m（i>m时a_i与b_i的关系不用考虑），那么称a_p, 1≤p≤n的字典序小于b_q, 1≤q≤n。由这个定义可以很容易的发现这样一个事实，当同样长度的一串数值、字符串需要按照字典序排列时，进行比较的位数i总是从n递减至1，例如：1234<1243, 1234<1342, 1243<1342，所以这三个串的顺序是：1234<1243
<1342，比较的位数依次是第3位和第2位；而从高位降低一位进行比较的条件则是对于此时的i，有a_i+1≥a_i+2≥…≥a_i+n，例如当i=2时，12345<12354<12534<12543，此时a₃≥a₄≥a₅，于是接下来将把2替换成字典中下一个数字3来进行排列，这个特点将在本文的最后一个方法中得到应用。

二、利用递归解决全排列问题

下面就让我们来看一个具体问题，给定一串数字：{a₁, a₂, …, a_n}，它们两两之间并不重复，要求输出由这些数字组成的全排列。乍看之下似乎可以用穷举法解决，由于n个数字的全排列个数是n!，故而穷举法的时间复杂度为O(n)。那么利用什么数据结构来穷举呢，由于全排列我们需要考虑每一位的各种情况，确定了一位的数字以后就继续试验下一位……也就是说当确定一种可能性之后就会沿着这条路径一直往下，直到确定最后一位数字，这个行为和深度优先搜索算法比较相似，因此我们可以用树来表示穷举的全过程，下图以求{1,2,3}的全排列为例如此方法进行说明：

图一 利用递归生成{1,2,3}的全排列

从上图我们可以看到，每一个排列就是从根结点到叶子结点的一次遍历，其伪代码如下：

三、含有重复数字的全排列问题

上述方法很直观，可是存在着一个问题，那就是它无法判断出某些数是否重复，它只是很单纯的穷举着所有可能出现的排列，例如1,2,2,4这四个数实际排列数为：4!/2!=12种，而上述算法仍然会得出24个结果，它无法区分1,2,2,4和1,2,2,4是一个重复的排列，应该只列举一次。可是递归的方法又非常直观非常方便啊，应该怎么办呢？其实只要在原方法上做一点小改动，人为的多设置一个集合，该集合包含了原集合中所有不重复的数字，从而树同一级的分支用该集合中的数字做为标签进行搜索，这样能够避免同一级出现重复计算的情况，下面以1,2,2为例说明上述方法的错误以本方法的改进：

  图二 传统方法处理有重复数字的集合时会产生非预期的结果

改进后的伪代码：

从代码中可以看出改进方法只是用一个不包含有重复元素的集合来代替原集合，并用新的集体进行迭代，转化成树形结构如下图所示：

图三 改进方法生成全排列

听老师上课的时候说这是一道微软来我们学校面试的考题，其实高爷爷在TAOCP第四卷分册2用了整个分册的内容讨论了如何生成全n元组(n-tuples)和全排列的问题，书中所述的第一个按字典序生成全排列的方法即可以在不必考虑给出的数集中是否有重复数字的情况下完美的生成全排列：

四、Algorithm L in TAOCP （字典序排列的生成）

Algorithm L是一个很经典的算法，它简单、灵活，对于给定的输入a₁, a₂, …, a_n（要求该输入必须是排好序的，即a₁ ≤ a₂≤ … ≤ a_n）可以生成该集合的全排列，按字典序输出，并且可以很好的处理给定的输入中有重复数字的情况。注意到这个算法对于输入的要求必须是有序的，而前面两个算法无论输入的顺序是递增、递减、乱序都可以很好的工作。

这个算法还有一个特点就是它的输出将排列按照字典序输出，那么在设计算法的时候肯定会需要用到字典序的一些特点，让我们来回顾一下上文所述——字典序的比较是从最高位开始逐渐递减至最低位，每次递减的时机是从该位开始至最高位，所有的数字呈从大到小的顺序排列，明白了这个特点就能够很轻松的理解L算法。

让我们先来看一下L算法的思路：

1. 找到能够满足下一步递增a_j的索引j，即当前比较的位数j
2. 将a_j递增到尽可能小的下一个值
3. 将a₁…a_j开始的排列置于当前最适合的字典序模式（即a_j+1至a_n按从小到大的顺序排列）

L算法基本上按照思路，共分成4步

L1. [输出] 输出排列a₁…a_n；
L2. [找到j] 令j←n-1，如果a_j≥a_j+1则将j自减1，直到a_j<a_j+1。这步的作用就是找到使从j位至最高位所有的数字呈从大到小的顺序排列的这个j，该位就是下一步需要改变（增加）的值。
L3. [更改a_j] 令l←n，如果a_j≥a_l则将l自减1，直到出现a_j<a_l，（updated 此时交换a_j←→a_l）
。这步的作用就是找到从第j位至最高位中，大于a_j的最小数值，该数值就是下一个字典序中a_j的值。
L4. [反转a_j...a_n] 令k←j+1，l←n，如果k<l，交换a_k←→a_l，自增k，自减l，再重复此交换直到k≥l。这步的作用是使由a₁…a_j开头的排列恢复到字典序的最小位置。

这种文字的步骤似乎比较难以理解，下面一个例子对算法的步骤加以说明：

(1) 整个算法的核心就是找到需要改变的j值，例如13287651，注意到最后四位已经按照从大到小的顺序排列，也就是说13287651是处于132xxxxx这个排列在字典中的最大值，那么下一个排列就要通过修改第3位的2获得。——这是L2.步骤解决的问题
(2) 那么这个2要替换成什么数值才行呢，在132之后一共有五个数字，1,5,6,7,8，让我们来比较它们的大小：13187652<13287651<13587621<13687521<13782651<13827651，可以看到，在字典中紧跟着13287651的排列是13587621，也就是将要替换的2与后面所有数值中大于2的最小数字进行代换。——这是L3.步骤解决的问题
(3) 在替换了2之后，排列变为了13587621，注意到在寻找j的时候我们已经保证了最后五位是按从大到小的顺序排列的，又由于替换的数字是大于a_j所有数字当中最小的，所以在替换之后我们仍可以得到一个有序的数列，这个数列是135xxxxx这个形式的所有排列中最大的，于是我们要对它进行反转，这样得到的数列顺序为从小到大，同时也是所有排列中最小的。——这是L4.步骤解决的问题。

之前看到有关求全排列的问题时我也常常看到介绍的就是这个通用算法，可惜当时一直没有认真去琢磨其中每步的作用，所以一直对这个问题敬而远之，在高爷爷的书中还有介绍更多更详细的算法，出于敬畏我有时间了再研读它吧。

五、参考文献

1. Permutation (wikipedia):
http://en.wikipedia.org/wiki/Permutation

2. Lexicographical order (wikipeida):
http://en.wikipedia.org/wiki/Lexicographic_ordering

3. Donald Knuth. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 0-201-85393-0.