本文简述了两种生成排列的方法
生成排列的方法不少,一种经典的方法就是采用递归,假设我们需要求解 1 ~ n 的所有排列,那么我们假设已经求解了 1 ~ n - 1 的所有排列,然后对于求解出的每一种排列(1 ~ n - 1 的一种排列),我们将 n 放置于该排列中可能的 n 个空位上,即可完成 1 ~ n 的排列求解.
说的有些抽象,举个实际的例子:
假设我们要求解 1 ~ 3 这三个数字的所有排列,并且我们已经求解出了 1 ~ 2 的所有排列,求解出的排列如下所示:
1,22,1 begin{aligned} 1, 2 \ 2, 1 end{aligned} 1,22,1
其中每个排列都有 3 个空位:
empty 1,empty 2 emptyempty 2,empty 1 empty begin{aligned} boxed{empty} 1, boxed{empty} 2 boxed{empty} \ boxed{empty} 2, boxed{empty} 1 boxed{empty} end{aligned} empty 1,empty 2 emptyempty 2,empty 1 empty
我们将 3 依序填入每个空位即可完成 1 ~ 3 排列的求解:
3,1,21,3,21,2,33,2,12,3,12,1,3 begin{aligned} boxed{3}, 1, 2 \ 1, boxed{3}, 2 \ 1, 2, boxed{3} \ boxed{3}, 2, 1 \ 2, boxed{3}, 1 \ 2, 1, boxed{3} end{aligned} 3,1,21,3,21,2,33,2,12,3,12,1,3
求解排列的另外一种思路,就是给每个可能的排列规定一个大小次序,仍然拿 1 ~ 3 的排列举例,我们可以规定:
1,2,3<1,3,2<2,1,3<2,3,1<3,1,2<3,2,1 begin{aligned} & 1, 2, 3 < 1, 3, 2 < 2, 1, 3 < 2, 3, 1 < 3, 1, 2 < 3, 2, 1 end{aligned} 1,2,3<1,3,2<2,1,3<2,3,1<3,1,2<3,2,1
即排列 1,2,31, 2, 31,2,3 最小,排列 3,2,13, 2, 13,2,1 最大,扩展到 1 ~ n 的排列来讲,如果给定一个现有排列(初始即为 1 ~ n 的顺序排列: 1,2,3,...,n1, 2, 3, ..., n1,2,3,...,n),我们生成大于该排列的最小排列,依次进行下去便可生成所有排列.
那么如何生成大于该排列的最小排列呢?方法如下:
假设当前给定的排列为 a1,a2,a3,a4,...ana_1, a_2, a_3, a_4, ... a_na1,a2,a3,a4,...an
- 从后(ana_nan 开始)往前查找,找到第一个满足 ai<ai 1a_i < a_{i 1}ai<ai 1 的元素
- 再次从后(ana_nan 开始)往前查找,找到第一个满足 aj>aia_j > a_iaj>ai 的元素(aia_iai 为上一步骤的结果元素)
- 交换 aia_iai 和 aja_jaj
- 将 ai 1a_{i 1}ai 1 至 ana_nan 的元素重新排序
(这里我们只给出了过程描述,更多细节大家可以参考相关书籍)
有了算法步骤,我们便可以进行代码实现了,过程中有两点值得一提:
- 如果第 1 步中找不到满足 ai<ai 1a_i < a_{i 1}ai<ai 1 的元素怎么办?这种情况会出现在元素逆序的排列中(譬如排列: 3,2,13, 2, 13,2,1),处理方法很简单,我们直接跳过 2, 3 步骤,直接执行第 4 步中的排序即可,由于此时元素是逆序的,我们直接反转(reverse)排列元素即可完成排序(排序之后排列又回到了"原点").
- 如果正常进行了 1, 2, 3 这三个步骤,第 4 步中的重新排序操作我们仍然可以通过直接反转(reverse)排列元素来完成:
考虑第 1 步骤的操作,当找到目标元素 aia_iai 时,我们可知以下元素关系:
ai<ai 1>ai 2>ai 3>...>an a_i < a_{i 1} > a_{i 2} > a_{i 3} > ... > a_n ai<ai 1>ai 2>ai 3>...>an
考虑第 2 步骤的操作,当找到目标元素 aja_jaj 时,我们可知以下元素关系:
...>aj−1>aj>ai>aj 1>... ... > a_{j-1} > a_j > a_i > a_{j 1} > ... ...>aj−1>aj>ai>aj 1>...
第 3 步骤我们执行了 aia_iai 与 aja_jaj 的交换,根据之前的元素关系,我们可知:
aj<ai 1>ai 2>...>aj−1>ai>aj 1>...>an boxed{a_j} < a_{i 1} > a_{i 2} > ... > a_{j-1} > boxed{a_i} > a_{j 1} > ... > a_n aj<ai 1>ai 2>...>aj−1>ai>aj 1>...>an
所以 ai 1a_{i 1}ai 1 至 ana_nan 间的元素在 1, 2, 3 步骤之后仍然是逆序关系,自然我们就可以通过直接反转(reverse)这些元素来对它们进行排序了,最终的示例代码如下:
代码语言：javascript复制// C#
public static List<int> NextPermutation(List<int> curPermutation)
{
var swapIndex = -1;
var index = curPermutation.Count - 2;
while (index >= 0)
{
if (curPermutation[index] < curPermutation[index 1])
{
swapIndex = index;
break;
}
--index;
}
if (swapIndex >= 0)
{
// valid swap index, swap with the rest smallest big number
var swapElement = curPermutation[swapIndex];
var smallIndex = swapIndex 1;
for (int i = curPermutation.Count - 1; i >= swapIndex 2; --i)
{
if (curPermutation[i] > swapElement)
{
smallIndex = i;
break;
}
}
// do swap
curPermutation[swapIndex] = curPermutation[smallIndex];
curPermutation[smallIndex] = swapElement;
}
// do sort
var startIndex = swapIndex 1;
var endIndex = curPermutation.Count - 1;
while (endIndex > startIndex)
{
var temp = curPermutation[startIndex];
curPermutation[startIndex] = curPermutation[endIndex];
curPermutation[endIndex] = temp;
startIndex;
--endIndex;
}
return curPermutation;
}
