今年Autodesk到我们那儿招聘实习生的题目是矩阵计算。其中要用到任意阶数的矩阵求逆。凭我线性代数55分的脑袋瓜，能理解的算法也就是最笨的那种啦～中间还要求任意阶数的行列式的值，想想就头疼。结果在慌乱之间，必要的一步n个数的全排列生成也不会写了。结果自然是“可耻的失败鸟…”，一怒之下，回来补完！
第一次看到这个算法是在软件设计师的辅导书上。代码如下，在VC++ 7.0下调试通过。
// Permutation.cpp : 定义控制台应用程序的入口点。
//
//N个数全排列的非递归算法
#include "stdafx.h"
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
/*
根据当前的排列p，计算下一个排列。
原则是从1234-->4321，若p已经是最后一个排列，传回false，否则传回true。
p是一个n维向量。
*/
bool nextPermutation(int *p, int n)
{
int last = n - 1;
int i, j, k;
//从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。
i = last;
while (i > 0 && p[i] < p[i - 1])
i--;
//若没有后面的数大于前面的数的情况，说明已经到了最后一个排列，返回false。
if (i == 0)
return false;
//从后查到i，查找大于p[i - 1]的最小的数，记入k
k = i;
for (j = last; j >= i; j--)
if (p[j] > p[i - 1] && p[j] < p[k])
k = j;
//交换p[k]和p[i - 1]
swap(p[k], p[i - 1]);
//倒置p[last]到p[i]
for (j = last, k = i; j > k; j--, k++)
swap(p[j], p[k]);
return true;
}
//显示一个排列
void showPermutation(int *p, int n)
{
for (int i = 0; i < n; i++)
cout << p[i];
}
int _tmain(int argc, _TCHAR* argv[])
{
int n;
int *p;
cin >> n;
p = new int[n];
for (int i = 0; i < n; i++)
p[i] = i + 1;
showPermutation(p, n);
cout << endl;
while(nextPermutation(p, n))
{
showPermutation(p, n);
cout << endl;
}
delete[] p;
system("pause");
return 0;
}
这个算法挺难理解的。这里试图说明一下算法的意思。
主要的任务在nextPermuation()中完成。这其中的思想是，提供一个已经有的全排列P，求出P的“下一个”全排列。这里“下一个”的意思是说，在n个数的n!个全排列在数字上从小到大的一个序列中，p的下一个数字上比它大的一个排列。
那么由此，提供一个初始的n个数的全排列P1 = p1p2…pn，有pi > pi – 1(1 < i < n – 1)，反复运行nextPermuation()找出比P的“下一个”全排列，直到Pn! = p1’p2’…pn’，pi < pi – 1
(1 < i < n – 1)为止。所找到的所有的排列就是n的全排列。
(1 < i < n – 1)为止。所找到的所有的排列就是n的全排列。
下面要考虑的问题，是如何从一个已知的排列P = p1p2…pn，找到它的下一个排列
Q = q1q2…qn。我们要让排列从小到大生成，简单说，要让排列的趋势从p1p2…pn，pi > pi – 1(1 < i < n – 1)，到p1’p2’…pn’，pi < pi – 1(1 < i < n – 1)。因此：
Q = q1q2…qn。我们要让排列从小到大生成，简单说，要让排列的趋势从p1p2…pn，pi > pi – 1(1 < i < n – 1)，到p1’p2’…pn’，pi < pi – 1(1 < i < n – 1)。因此：
1. 从低位到高位（从后向前），找出“不符合趋势”的数字。即找到一个pi，使pi – 1 < pi。若找不到这样的pi，说明我们已经找到最后一个全排列，可以返回了。
2. 把pi － 1替换成从pn到pi几个数字中“刚刚好大于pi-1”的数字。这里的目的是找出准确的P的下一个排列Q。所谓“刚刚好大于”，我们就查找从pi到pn中大于pi-1的最小的数字。然后将找到的数字与pi-1交换。
3. 还没有结束。交换后，pi-1pi…pn并不是准确的后一个排列。因为根据第一步的查找，我们有pi > pi+1 > … > pn，否则查找在i～n就会停下来了。这样的一个排列显然不是最小的。实际上，原来的pi…pn，已经是这一部分最大的一个排列了。但我们现在换了最高位pi-1，因此要让后面的数字变的最小。方法很简单，根据上面的推理，我们只须将pi～pn的数列倒置即可（最大的排列倒置就变成了最小的排列）。
这样，我们计算出了准确的下一个排列。