全排列生成数字或者字母

《全排列生成数字或者字母》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第一次看到这个算法是在软件设计师的辅导书上。代码如下，在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) { i

2、nt 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

3、-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 an>int[n]; for (int i = 0;i <

4、 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的下一个数字上比

5、它大的一个排列。那么由此，提供一个初始的n个数的全排列P1=p1p2…pn，有pi>pi–1(1pi–1(1

6、不符合趋势”的数字。即找到一个pi，使pi–1pi+1>…>pn，否则查找在i～n就会停下来了。这样的一个排列显然不是最小的。实际上，原来的pi…pn，已经是这一部分最大的一个排列了。但我

7、们现在换了最高位pi-1，因此要让后面的数字变的最小。方法很简单，根据上面的推理，我们只须将pi～pn的数列倒置即可（最大的排列倒置就变成了最小的排列）。这样，我们计算出了准确的下一个排列。比如有(1,2,3,4)这样一组数1.先分成(1)和(2,3,4),然后对(2,3,4)全排列2.把(1)分别和(2,3,4)中的数对调3.比如一次调换(2),(1,3,4),然后对(2,3,4)全排列4.调换的算完了,恢复,变成(1),(2,3