全排列
定义从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m＝n时所有的排列情况叫全排列。
如1,2,3三个元素的全排列为：
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
全排列公式全排列数f(n)=n!(定义0!=1)
基本算法采用深度优先搜索算法，即对每一位上的数进行枚举而求得所有排列。一般利用递归完成。
全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排列数为n!个。现以{1, 2, 3, 4, 5}为
例说明如何编写全排列的递归算法。
1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。
由于一个数的全排列就是其本身，从而得到以上结果。
2、再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。
即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.
从而可以推断，设一组数p = {r1, r2, r3, ... ,rn}, 全排列为perm(p)，pn = p - n。
因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)。当n = 1时perm(p} = r1。
为了更容易理解，将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。
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);
}[1]
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);
}
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);
}
}
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
'C源代码参考了http://blog.csdn.net/no_end_point/archive/2008/03/06/2153247.aspx
'修改: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;i<=m;i++)cout<<list;
cout<<endl;
}
else//还有多个元素待排列，递归产生排列
for(int i=k;i<=m;i++)//循环交换第一个元素与其后的所有元素实现全 //排列
{
Swap(list[k],list);
Perm(list,k+1,m);
Swap(list[k],list);
}
}
我有一个非递归算法
#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;
}