全排列生成数字或者字母.doc

第一次看到这个算法是在软件设计师的辅导书上。代码如下，在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?anint[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的全排列。 下面要考虑的问题，是如何从一个已知的排列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)。因此： 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的数列倒置即可（最大的排列倒置就变成了最小的排列）。 这样，我