下载掌阅APP，畅读海量书库
立即打开
排列就是将元素（或符号）按照确定的顺序进行重排，重排后的每一个顺序称为一个排列。例如，对于元素集 S =｛1，2，3｝而言，可获得6个排列 p 1 =（1，2，3）， p 2 =（1，3，2）， p 3 =（2，1，3）， p 4 =（2，3，1）， p 5 =（3，1，2）， p 6 =（3，2，1）。从 n 个不重复元素中任取 m 个元素，这 m 个元素构成的所有不同排列的个数称为排列数，记为A m n 或 A （ n ， m ），计算公式如式（3.1）所示。
其中！表示阶乘。以
为例，共有3个位置可以放置元素，第1个位置所有6个元素都可以放置，第2个位置只有5个元素可以放置，第3个位置只有4个元素可以放置，可构成的排列数为
。
当 m = n 时，构成的排列称为全排列。根据 S =｛1，2，3｝获得的全排列结果可以看出，参与全排列的元素 s i 在排列的所有位置均出现过，每次都构成一个新的排列。因此，生成全排列的过程就是寻找一种映射规则，让参与排列的每个元素在排列的各位置出现一次。对于有 n 个元素的集合 S =｛ s 1 ， s 2 ，…， s n ｝，生成其对应的全排列过程可以描述为：取集合中任一元素 s i ，将其置于排列中的第1个位置 p 1 ，则求全排列 p 1 p 2 … p n 就变成了求以 s i 为首元素的子排列问题。同理，分别将 s i 置于 p 2 ， p 3 ，…， p n 处均可获得对应的子排列。合并所有子排列就能获得 S =｛ s 1 ， s 2 ，…， s n ｝对应的全排列。求解子排列与求解原排列使用相同的处理方法，但子排列的规模为 n -1，当只有一个元素时求解结束。因此，求解全排列具有典型的递归特性，可以通过递归来枚举生成排列树的方式求解全排列问题。假定待处理的元素集合为 S =｛ s 1 ， s 2 ，…， s n ｝，令 S i = S - s i ，用 P （ S ）表示 S 的全排列，（ s i ） P （ S i ）表示由 S i 的每一个排列加上前缀 s i 构成的排列，则全排列可用式（3.2）进行描述。
图3-2给出了集合为｛1，2，3，4｝时的全排列枚举树。
对一个无重复元素的有限集或其子集进行全排列时，可以按照最朴素的方法以递归的方式进行求解。
求有 n 个不重复元素的全排列的基本思路如下。
（1）先取出集合中的第1个元素 s 1 作为排列第1位，将其余的 n -1个元素 S n -1 =｛ s 2 ， s 3 ，…， s n ｝进行全排列。之后，分别将集合中第2个元素 s 2 ，第3个元素 s 3 ，…，第 n 个元素 s n 与 s 1 交换位置，求解剩余 n -1个元素构成的全排列。如图3-2所示，先取 s 1 =1，将其作为排列结果的第1位，然后求解由｛2，3，4｝构成的全排列；将 s 2 =2与 s 1 =1交换位置，将 s 2 =2作为排列结果的第1位，然后求解由｛1，3，4｝构成的全排列；以此类推，分别将 s 3 =3和 s 4 =4与 s 1 =1交换位置，求解对应的全排列。
（2）对 n -1个元素进行全排列时，同样先确定第1位，然后其余 n -2个元素进行全排列，以此类推，直至集合中只余一个元素时结束。从分析过程中可以看出，问题和子问题的求解方法是相同的，与原问题相比，子问题的规模不断缩小，当 n =1时，处理结束。这是典型的递归求解问题。
图3-2 集合为｛1，2，3，4｝时的全排列枚举树
为了便于处理，假定需要进行排列的元素均为字符型。建立swap_element（）函数，该函数用于交换集合中的两个元素。函数有3个参数，list［］为构成排列的字符元素集合，m和n为待交换值的两个元素对应的下标。
实现朴素全排列功能的函数为native_all_perm（）。native_all_perm（）函数为递归函数，实现从list［］集合中start至last范围内元素的全排列，使用current表示本次递归过程中的当前位置。函数有4个参数，list［］为元素集合，start为起始位置下标，current为当前位置下标（递归时使用），last为终止位置下标。
当前递归位置current到达last时，说明已经实现了某个排列，到达出口，可以输出该排列。未到达出口时，从current至last，依次交换i与current位置的元素，然后再进行全排列。
实现代码如下。
在循环内部，首先将当前元素list［current］与集合中的第i个元素list［i］交换位置，然后求解以list［i］开头、由集合中剩余元素构成的全排列，再将list［current］恢复到原来位置准备进行下一次处理。
需要注意的是，求解子排列后，数据处于“脏”状态，必须将list［current］恢复到原来位置，否则会导致部分排列未能正确生成和出现重复排列等问题。例如，集合｛2，3，4｝在选定第一个元素2的前提下，将求解2｛3，4｝构成的子排列，先后形成［2 3 4］和［2 4 3］；交换第1元素2和第2元素4后，将元素4置于第一个位置，将求解4｛2，3｝构成的子排列，先后形成［4 2 3］［4 3 2］；继续交换第1元素4和第3元素2，将会导致重复求解2｛3，4｝子排列。因此，在递归求解过程中必须将交换后的元素还原到其初始位置以确保下次交换正常进行。
至此，已经实现了 n 个不重复元素的全排列。但元素集合中有重复元素的情况尚未解决，例如元素集合为｛ a ， b ， b ｝时，交换后会出现两个值相同的重复排列。因此，需要解决全排列的去重问题，需要对当前算法进一步改进。
若元素集合中存在重复元素，生成全排列时需要解决重复问题，例如abb形式只应输出一次。生成消除重复元素的全排列的主体函数是all_perm（）函数，参数与朴素全排列函数native_all_perm（）相同，处理流程基本一致，唯一变化的是在进行进一步递归生成排列前调用了need_swap（）函数。
need_swap（）函数用于判定当前元素与之前的元素间是否存在重复，是实现消除重复全排列的关键。该函数有3个参数，list［］、current和i，作用和意义与朴素全排列函数native_all_perm（）相同。去重全排列的根本在于当前元素只需要与它前面出现的非重复字符交换。因此，need_swap（）函数增加了判断条件，判定两个待交换元素的值是否相同，若相等则表示元素值重复无须交换，不相同则应进行交换。
本部分代码将朴素全排列函数与消除重复情况的全排列函数合并到同一段代码中，在主函数中进行测试。
（1）无重复情况。
当输入数据为abcdef 1 3时，运行结果如下（无重复情况）。
（2）有重复情况。
当输入数据为abccd 1 3时，运行结果如下（有重复）。
