从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m＝n时所有的排列情况叫全排列。

简介

如果用递归算法结果是

全排列公式

基本算法((A)字典序法 B 递增进位制数法 C 递减进位制数法 D 邻位对换法)

下面来说说全排列问题的递归与非递归解法.(1.递归(分治法思想): 2.非递归:)

C语言实现Heap算法全排列

Java 源代码实现

Pascal源代码

VB源代码(用字典序法实现全排列（VC++实现）)

简介

如1,2,3三个元素的全排列为：

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

如果用递归算法结果是

1,2,3

1,3,2

2,1,3

2,3,1

3,2,1

3,1,2

这是由于算法只是考虑到了如何输出全排列，而没有考虑到换位是否有问题。所以我提出了解决方案，就是换位函数修改下

如 1 2 3 换位的话 ,不应该直接 3 2 1这样 ,让3和1直接换位; 而是让3排在最前后 ,1 2 依次向后

全排列公式

全排列数f(n)=n!(定义0!=1)

基本算法

以下介绍全排列算法四种：

(A)字典序法

(B)递增进位制数法

(C)递减进位制数法

(D)邻位对换法

(A)字典序法

对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。 [例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。

[注意] 一个全排列可看做一个字符串，字符串可有前缀、后缀。

1）生成给定全排列的下一个排列 所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。

B 递增进位制数法

1)由排列求中介数 在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。

在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2—n)一致。可看出n-1位的进位链。 右端位逢2进1，右起第2位逢3进1，…， 右起第i位逢i+1进1，i=1,2,…,n-1. 这样的中介数我们称为递增进位制数。 上面是由中介数求排列。

由序号（十进制数）求中介数（递增进位制数）如下：

m=m1,0≤m≤n!-1

m1=2m2+kn-1,0≤kn-1≤1

m2=3m3+kn-2,0≤kn-2≤2

……………

mn-2=(n-1)mn-1+k2,0≤k2≤n-2

mn-1=k1,0≤k1≤n-1

p1p2…pn←→(k1k2…kn-1)↑←→m

在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。

为方便起见，令ai+1=kn-1，i=1,2,…,n-1

(k1k2…kn-1)↑=(anan-1…a2)↑

ai：i的右边比i小的数字的个数

在这样的定义下，

有839647521←→(67342221)↑

(67342221)↑+1=(67342300)↑←→849617523

6×8+7)×7+3)×6+4)×5+2)×4+2)×3+2)×2+1 =279905

由(anan-1…a2)↑求p1p2…pn。

从大到小求出n,n-1,…,2,1的位置

_ ... _ n _ _ …_ (an个空格)

n的右边有an个空格。

n-1的右边有an-1个空格。

…………

2的右边有a2个空格。

最后一个空格就是1的位置。

C 递减进位制数法

在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。 (anan-1…a2)↑→(a2a3…an-1an)↓

839647521→ (12224376)↓

(12224376)↓=1×3+2)×4+2)×5+2)×6+4)×7+3)×8+7)×9+6=340989

[注意]求下一个排列十分容易

D 邻位对换法

递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。 这个算法可描述如下：

对1—n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1—n的n个排列。

对1—n-1的每一个奇排列，n从左到右插入n个空档，生成1—n的n个排列。

对[2,n]的每个数字都是如此。

839647521

字典序法 递增进位制法 递减进位制法 邻位对换法

下一个 839651247 849617523 893647521 836947521

中介数 72642321↑ 67342221↑ 12224376↓ 10121372↓

序 号 297191 279905 340989 203393

下面来说说全排列问题的递归与非递归解法.

1.递归(分治法思想):

设R={r1,r2,..rn} 是要进行排列的n个元素,Ri=R-{ri}.集合X中元素的全排列记为perm(X);

设(ri)perm(X)表示每一个全排列前加上前缀ri得到的排列.当n=1时,perm(R)=(r) 其中r是唯一的元素,这个就是出口条件.

当n>1时,perm(R)由(r1)perm(R1),(r2)perm(R2),...(rn)perm(Rn)构成.

void Perm(list[],int k,int m) //k表示前缀的位置,m是要排列的数目.

{

if(k==m-1) //前缀是最后一个位置,此时打印排列数.

{

for(int i=0;i<m;i++)

{

printf("%d",list[i]);

}

printf("n");

}

else

{

for(int i=k;i<m;i++)

{

//交换前缀,使之产生下一个前缀.

Swap(list[k],list[i]);

Perm(list,k+1,m);

//将前缀换回来,继续做上一个的前缀排列.

Swap(list[k],list[i]);

}

}

}

//此处为引用,交换函数.函数调用多,故定义为内联函数.

inline void Swap(int &a,int &b)

{

int temp=a,a=b,b=temp;

}

函数Perm(int list[],int k,int m)是求将list的第0~k-1个元素作为前缀、第k~m个元素进行全排列得到的全排列，如果k为0，且m为n，就可以求得一个数组中所有元素的全排列。其想法是将第k个元素与后面的每个元素进行交换，求出其全排列。这种算法比较节省空间。

2.非递归:

n个数的排列可以从1.2....n开始,至n.n-1....2.1结束。

也就是按数值大小递增的顺序找出每一个排列。

以6个数的排列为例，其初始排列为123456,最后一个排列是654321,

如果当前排列是124653,找它的下一个排列的方法是，从这个序列中

从右至左找第一个左邻小于右邻的数，如果找不到，则所有排列求解

完成，如果找得到则说明排列未完成。本例中将找到46,计4所在的

位置为i,找到后不能直接将46位置互换，而又要从右到左到第一个

比4大的数，本例找到的数是5，其位置计为j，将i与j所在元素交换

125643,然后将i+1至最后一个元素从小到大排序得到125346，这

就是124653的下一个排列，如此下去，直至654321为止。算法结束。

int b[N];

int is_train(int a[],int n)

{

int i,j,k=1 ;

for(i=1;i<=n;i++)

{

for(j=i+1;j<=n;j++)

if(a[j]<a[i])b[k++]=a[j];

/*判断是否降序*/

if(k>1)is_train(b,k);

else return(1);

}

}

void train(int a[],int n)

{

int i,j,t,temp,count=1 ;

t=1 ;

printf("input the %3dth way:",count);

for(i=1;i<=n;i++)

printf("%3d",a[i]);

printf("n");

while(t)

{

i=n ;

j=i-1 ;

/*从右往左找,找第一个左邻比右邻小的位置*/

while(j&&a[j]>a[i])

{

j--;

i--;

}

if(j==0)t=0 ;

else t=1 ;

if(t)

{

i=n ;

/*从右往左找,找第一个比front大的位置*/

while(a[j]>a[i])

i--;

temp=a[j],a[j]=a[i],a[i]=temp ;

quicksort(a,j+1,N);/*调用快速排序*/

/*判断是否符合调度要求*/

if(is_train(a,N)==1)

{

count++;

printf("input the %3dth way:",count);

for(i=1;i<=n;i++)

printf("%3d",a[i]);

printf("n");

}

}

}

}

C语言实现Heap算法全排列

#include <stdio.h>

#define MAX 100

void process(char *c,int n){

int i = 0;

while(i < n){

printf("%c",c[i]);

i++;

}

printf("\");

}

void perm(char *list,int n){

int k;

char tmp;

int i = n;

int count[MAX];

count[i - 1] = 1;

while(i > 2){

i--;

count[i - 1] = 1;

}

process(list,n);

do{

if(count[i - 1] < i){

if(i % 2 != 0)

k = 1;

else

k = count[i - 1];

tmp = list[k - 1];

list[k - 1] = list[i - 1];

list[i - 1] = tmp;

count[i - 1] += 1;

i = 2;

process(list,n);

}else{

count[i - 1] = 1;

i += 1;

}

}while(i <= n);

}

int main(){

char c[] = {'a','b','c','d'};

perm(c,4);

}

Java 源代码实现

public class Test {

public static char[] text = { 'a', 'b', 'c', 'd', 'e' };

public static void main(String[] args) {

permutation(text, 0, text.length);

System.exit(0);

}

/**

* 全排列输出

*@param a[] 要输出的字符数组

*@param m 输出字符数组的起始位置

*@param n 输出字符数组的长度

*/

public static void permutation(char a[], int m, int n) {

int i;

char t;

if (m < n - 1) {

permutation(a, m + 1, n);

for (i = m + 1; i < n; i++) {

t = a[m];

a[m] = a[i];

a[i] = t;

permutation(a, m + 1, n);

t = a[m];

a[m] = a[i];

a[i] = t;

}

} else {

printResult(a);

}

}

/**

* 输出指定字符数组

*@param 将要输出的字符数组

*/

public static void printResult(char[] text) {

for (int i = 0; i < text.length; i++) {

System.out.print(text[i]);

}

System.out.println();

}

}

Pascal源代码

program e;

var

n,t:longint;

a:array[1..8] of integer;

flag:array[1..8] of boolean;

procedure search(depth:integer); {depth变量表示正在搜索第几个元素}

var

i:integer;

begin

if(depth>n) then {depth>n表明已经搜索到了第n个数，那么输出结果}

begin

for i:=1 to n do write(a[i]:4);

writeln;

inc(t);

exit; {此种结果输出后，退出该层搜索}

end;

for i:=1 to n do {枚举下一个出现的元素}

if flag[i]=false then {判断是否已经出现过}

begin

a[depth]:=i; {没有出现，则把第depth个数设为i}

flag[i]:=true; {给这个标志变量给出出现的标志}

search(depth+1); {递归搜索下一个元素}

flag[i]:=false; {回溯，此时恢复这个标志变量为没出现的标志}

end;

end;

begin

writeln('input N:');

read(n);

t:=0;

fillchar(flag,sizeof(flag),false); {赋初值，设定全部没有出现过}

search(1);

writeln('Total=',t);

end.

VB源代码

Option Explicit

'修改:TZWSOHO

Private Sub Command1_Click()

Dim nt As Double: nt = Timer

List1.Visible = False: List1.Clear

Permutation "", Text1.Text

List1.Visible = True

Debug.Print Timer - nt,

End Sub

'递归求全排列

'算法描述:

'以8位为例，求8位数的全排列，其实是8位中任取一位

'在后加上其余7位的全排列

'7 位：任取一位，其后跟剩下6位的全排列

'……

'这样就有两部分，一部分为前面的已经取出来的串，另一部分为后面即将进行的全排列的串

'参数pre即为前面已经取出来的串

'参数str即为将要进行排列的串

Private Sub Permutation(pre As String, s As String)

Dim i As Long

'// 如果要排列的串长度为1，则返回

If Len(s) = 1 Then List1.AddItem pre & s: Exit Sub

'// for循环即是取出待排列的串的任一位

For i = 1 To Len(s)

'// 递归，将取出的字符并入已经取出的串

'// 那么剩下的串即为待排列的串

Permutation pre & Mid$(s, i, 1), Left$(s, i - 1) & Mid$(s, i + 1)

Next

End Sub

C++实现

template < class Type>

void Perm(Type list[],int k,int m)

{//产生list[k:m]的所有全排列

if(k == m)

{//只剩一个元素

for(int i=0;i<=m;i++)cout<<list[i];

cout<<endl;

}

else//还有多个元素待排列，递归产生排列

for(int i=k;i<=m;i++)//循环交换第一个元素与其后的所有元素实现全 //排列

{

Swap(list[k],list[i]);

Perm(list,k+1,m);

Swap(list[k],list[i]);

}

}

我有一个非递归算法

#include<stdio.h>

int *n;

void arge( int *x,int size)

{

int *t;

int totoal=0;

int pos=size-2;

int just=0;

t=new int;

for( int i=0 ;i<size; i++)

t=1;

while(1)

{

for( i=0 ; i<size; i++)

printf("%d ",x);

printf("\");

totoal++;

pos=size-2;

while(x[pos]>x[pos+1]) //

{

pos--;

t[x[pos+1]-1]=0;

}

if(pos<0)

break;

t[x[pos+1]-1]=0; //复位上一个

t[x[pos]-1]=0;

for( i=x[pos]+1; i<=size; i++)

{

if(t[i-1]==0)

{

x[pos]=i;

t=1;

break;

}

}

t[x[pos]-1]=1;

for( i=pos+1; i<size; i++)

{

for( int j=1; j<=size; j++)

{

if(t[j-1]==0)

{

x=j;

t[j-1]=1;

break;

}

}

}

}

printf("totoal= %d\",totoal);

delete [t];

}

int main()

{

int m;

scanf("%d",&m);

n=new int[m];

for( int i=0 ;i<m; i++)

n=i+1;

arge(n,m);

delete [n];

return 0;

}

用字典序法实现全排列（VC++实现）

#include <stdio.h>

int * array;

int num;

inline void xchg(int &a, int &b)

{

int c=a;

a=b;

b=c;

}

//从pos到num的数据进行翻转

void invert(int pos)

{

int count=num-pos+1;

for(int i=0; i<count/2; i++)

xchg(array[pos+i],array[num-i]);

}

//检查输入中是否有重复数值

bool is_valid(int data, int serial)

{

for(int i=1; i<serial; i++)

if(array[i]==data)

{

printf("全排列中不能有数据重复！\");

return 0;

}

return 1;

}

//输出全排列

void print_permutation(int m)

{

printf("之后第%d个全排列: ", m);

for(int i=1; i<=num; i++)

printf("%d ", array[i]);

printf("\");

}

//字典序全排列的主体

void dictionary()

{

printf("输入起始的全排列:\");

for(int i=1; i<=num; i++)

{

int data;

scanf("%d", &data);

if(is_valid(data,i))

array[i]=data;

else

return;

}

if(num==1)

{

printf("只有一个数，不需进行排列！\");

return;

}

int count;

printf("预测之后第几个序列：\");

scanf("%d", & count);

//一次循环找下一个全排列

for(int m=1; m<=count; m++)

{

int pos1=0;

int pos2;

//从num-1开始，找到第一个比右边值小的位置

for(int j=num-1; j>0; j--)

if(array[j]<array[j+1])

{

pos1=j;

break;

}

if(pos1<1 || pos1>num)

{

printf("目前全排列已为%d位数的最后一个全排列！\\",num);

return;

}

//从num开始找array[pos1]小的第一个数的位置

for(int n=num; n>pos1; n--)

if(array[n]>array[pos1])

{

pos2=n;

break;

}

xchg(array[pos1],array[pos2]);

//从pos1+1到num的数进行翻转

invert(pos1+1);

print_permutation(m);

}

}

void main()

{

printf("输入要进行全排列的位数\");

scanf("%d", &num);

array=new int[num+1];

while(1)

dictionary();

}