全排列生成数字或者字母

第一次看到这个算法是在软件设计师的辅导书上。代码如下，在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 an>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的全排列。

下面要考虑的问题，是如何从一个已知的排列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的数列倒置即可（最大的排列倒置就变成了最小的排列）。 这样，我们计算出了准确的下一个排列。

比如有(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,4),再调换下一个(3),(1,2,4)

大概就是这样的 -------------------------------- #include\int a[10],n,count=0; void perm(int k) { intp,t,j; if( k==n ) {count++;

for(p=1;p<=k;p++) printf(\中的数字是1，而不是字母l*/ printf(\

if( count%3==0 ) printf(\return;} for(j=k;j<=n;j++) {t=a[k];a[k]=a[j];a[j]=t; perm(k+1); t=a[k]; a[k]=a[j];a[j]=t;} } main() {int i;

printf(\scanf(\

for(i=1;i<=n;i++) a[i]=i; perm(1); }

#include

void swap(int&a, int&b) { int temp;

temp = a;

a = b;

b = temp; } /*

根据当前的排列p，计算下一个排列。

原则是从1234–>4321，若p已经是最后一个排列，传回false，否则传回true。

p是一个n维向量。 */

boolnextPermutation(int *p, int n) {

int last=n-1;

inti,j,k;

//从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。

本文来源：https://www.bwwdw.com/article/la7t.html