全排列算法原理和实现

本文为原创，如需转载，请注明作者和出处，谢谢！

全排列是将一组数按一定顺序进行排列，如果这组数有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 - {rn}。

因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)。当n = 1时perm(p} = r1。

为了更容易理解，将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。

算法如下：

#include <stdio.h>

int n = 0;

void swap(int *a, int *b)
{
    int m;
    m = *a;
    *a = *b;
    *b = m;
}
void perm(int list[], int k, int m)
{
    int i;
    if(k > m)
    {
        for(i = 0; i <= m; i++)
            printf("%d ", list[i]);
        printf("\n");
        n++;
    }
    else
    {
        for(i = k; i <= m; i++)
        {
            swap(&list[k], &list[i]);
            perm(list, k + 1, m);
            swap(&list[k], &list[i]);
        }
    }
}
int main()
{
    int list[] = {1, 2, 3, 4, 5};
    perm(list, 0, 4);
    printf("total:%d\n", n);
    return 0;
}

谁有更高效的递归和非递归算法，请回贴。

《Android开发完全讲义（第2版）》（本书版权已输出到台湾）
http://product.dangdang.com/product.aspx?product_id=22741502

《Android高薪之路：Android程序员面试宝典》http://book.360buy.com/10970314.html

新浪微博：http://t.sina.com.cn/androidguy 昵称：李宁_Lining

posted on 2008-05-11 15:43 银河使者阅读(7860) 评论(11) 编辑收藏所属分类: algorithm 、C/C++ 、原创

# re: 全排列算法原理和实现回复 更多评论

#include<cstdlib>
#include<iostream>
#define CHESSNUM 9
using namespace std;
/*********************************************************/
void Rank_Chess(int m);
int Change_Rank(int w);
bool Down_Rank(int x);
void Up_Rank(int m);
void Show();
/**********************************************************/
static char num[CHESSNUM];
static int counter[CHESSNUM];
static int num_counter=0;
/**********************************************************/
int main(){
for(int x=0;x<CHESSNUM;x++)
num[x]='A'+x;
Show();
for(int y=0;y<CHESSNUM;y++)
counter[y]=CHESSNUM-1;
Rank_Chess(CHESSNUM);
cout<<"\n\n\nAdd up to "<<num_counter<<" number."<<endl;
cout<<"\t\t\t\t---By 翟梦华"<<endl;
getchar();
return 0;
}
/**********************************************************/
void Rank_Chess(int m){
while(1){
if(m==2){char currency;
currency=num[CHESSNUM-1];
num[CHESSNUM-1]=num[CHESSNUM-2];
num[CHESSNUM-2]=currency;
Show();}
if(!(Down_Rank(m))) Rank_Chess(m-1); //recursive function
else {Change_Rank(m+1);break;}
}
}
/**********************************************************/
int Change_Rank(int w){
if(w>CHESSNUM) return 0;
if(counter[CHESSNUM-w]==CHESSNUM-w)
{counter[CHESSNUM-w]=CHESSNUM-1;return 0;}
{char currency;
currency=num[CHESSNUM-w];
num[CHESSNUM-w]=num[counter[CHESSNUM-w]];
num[counter[CHESSNUM-w]]=currency;
}
Up_Rank(w-1);counter[CHESSNUM-w]--;
return 0;
}
/**********************************************************/
bool Down_Rank(int x){
for(int i=CHESSNUM-2;i>CHESSNUM-x-1;i--)
if(num[i+1]>num[i]) return false;
return true;
}
/**********************************************************/
void Up_Rank(int m){
char alter[100];
for(int i=0;i<m;i++)
alter[i]=num[CHESSNUM-1-i];
for(int j=0;j<m;j++)
num[CHESSNUM-m+j]=alter[j];
Show();
}
/**********************************************************/
inline void Show(){
for(int x=0;x<CHESSNUM;x++)
cout<<num[x];
cout<<" |\t";
num_counter++;
}

这是我以前写的,虽然长了点有点啰嗦,但我测试过了,对9位数排列比你的快了13s.不信你自己试试.但我得承认你的代码写得很棒!

2008-07-26 18:36 | 翟梦华

# re: 全排列算法原理和实现回复 更多评论

哦,真是越看越惭愧,你的思路可要比我清晰多了。虽然大家用的都是递归之妙，但我写的东西真是太不成体统了。原本自己只学过2个礼拜的C便自以为已得算法之精妙，奈何山外有山。。。

2008-07-26 18:50 | 翟梦华

# re: 全排列算法原理和实现回复 更多评论

这是我的全排列 JAVA语言
package net.emlog.fei;

import java.util.Date;

public class ListAll {

/**
* @param args
*/
public static void main(String[] args) {

ListAll a = new ListAll();
String[] strings ={"a","d","c","d","e","f","g","h","i"};
String[] stringtt=null; ;
Date date = new Date(System.currentTimeMillis());
System.out.println(date.toString());
stringtt=a.returnAll(strings);
Date date1 = new Date(System.currentTimeMillis());
System.out.println(date1.toString());
for(int i = 0; i < stringtt.length;i++){
System.out.println(stringtt[i].toString());
}
}
/**
* 分析全排列我们发现其有这么一个规律即此数的全排列为在其前一个数的前排列所得到的数据的N个位置加上本身。1这本身
* 如2 21 12 为 returnAll(2) = returnAll(1)+n 和 n + returnAll(1)
* 3 为 m 0 to 2 returnAll(3) = returnAll(2)[t].subString(0,m) + n + returnAll(2)[t].subString(m); t 0 to returnAll(2).length
* 所以如下所示即可。
* 出于效率的考虑，我设置了两个变量。这两个变量如果根据题目要求可以不要，不过那样效率会很低。
* @param n
* @return
*/
private String[] returnAll(int n){
int length = 1;
for(int k = 1;k<=n;k++){
length = length*k;
}
String[] strings = new String[length];
if(n==1){
strings[0]=new Integer(n).toString();
}else{
String[] preStrings = returnAll(n-1);
String tmpString;
for(int t = 0 ; t<preStrings.length;t++){//数字的全排列的原数据来自于上一个上的全排列数组。
tmpString = preStrings[t];
for (int m =0 ;m<n ;m++){//上一个全排列数组中的某个数据从第0个索引开始到结束分别插入此数字
strings[t*n+m] = tmpString.substring(0, m)+ n +tmpString.substring(m);
}
}

}

return strings;
}

/**
* 可以随意编写字符来组成全排列数组
* @param x
* @return
*/
private String[] returnAll(String[] x){
int length = 1;
for(int k = 1;k<=x.length;k++){
length = length*k;
}
if(x.length !=length/(x[0].length()+1)){

}
String[] strings = new String[length];
if(x.length==1){
strings[0]=x[0];
}else{
String[] preStrings = returnAll(splitStrings(x));
String tmpString;
for(int t = 0 ; t<preStrings.length;t++){//全排列的原数据来自于上一个上的全排列数组。
tmpString = preStrings[t];
for (int m =0 ;m<x.length ;m++){//上一个全排列数组中的某个数据从第0个索引开始到结束分别插入此数据
strings[t*x.length+m] = tmpString.substring(0, m)+ x[x.length-1] +tmpString.substring(m);
}
}

}

return strings;
}
/**
* 以牺牲时间来换空间
* @param n
* @return
*/
private String[] returnAllInOne(int n){
int length = 1;
for(int k = 1;k<=n;k++){
length = length*k;
}
String[] strings = new String[length];
if(n==1){
strings[0]=new Integer(n).toString();
}else{
// String[] preStrings = returnAll(n-1);
// String tmpString;
for(int t = 0 ; t<returnAll(n-1).length;t++){
// tmpString = returnAll(n-1)[t];
for (int m =0 ;m<n ;m++){
strings[t*n+m] = returnAll(n-1)[t].substring(0, m)+ n +returnAll(n-1)[t].substring(m);
}
}

}

return strings;
}
/**
* 非1.6版本，生成除去数组的最后一位的数组
* @param strings
* @return
*/

private String[] splitStrings(String[] strings){
if(strings.length==0){return null;}
String[] tmpStrings = new String[strings.length-1];
for(int i =0;i<strings.length-1;i++){
tmpStrings[i]=strings[i].toString();
}
return tmpStrings;
}

}

对于9位数的排列未打印用时1秒分左右。

2008-07-31 14:46 | fei

# re: 全排列算法原理和实现回复 更多评论

#include<stdio.h>
#include<string.h>
#define MAX 100
int count=0;

void cr(int str[],int x,int y)
{
int i;
for(i=y-1;i>=x;i--)
str[i+1]=str[i];
str[i+1]=y;
if(x>y-1)
str[x]=y;
}

void hf(int str[],int x,int n)
{
int i;
for(i=x;i<n;i++)
str[i]=str[i+1];
}

void qpl(int str[],int m,int n)
{
int i;
if(m==n+1)
{
for(i=1;i<m;i++)
printf("%d",str[i]);
printf("\n");
count++;
return;
}
for(i=1;i<=m;i++)
{
cr(str,i,m);
qpl(str,m+1,n);
hf(str,i,m);
}
}

void main()
{
int n,str[MAX];
printf("请输入需要全排列的数：");
scanf("%d",&n);
qpl(str,1,n);
printf("%d",count);
}
对楼主的算法的另一种表述

2009-05-04 14:33 | ~~

# re: 全排列算法原理和实现回复 更多评论

#include <iostream>

using std::cout;
using std::endl;

void Print(int a[], int len, int n);

void PrintFullSeq(int n)
{
int* arr = new int[n];
for (int i=0; i<n; i++)
{
arr[i] = i+1;
}
Print(arr, n, n);
delete []arr;
}

void Print(int a[],int len, int n)
{
if (len==1)
{
for (int j=n; j>0; j--)
{
cout << a[j-1] <<" ";
}
cout << endl;
return;
}
for (int i=len-1; i>=0; i--)
{
int temp = a[i];
a[i] = a[len-1];
a[len-1] = temp;

Print(a, len-1, n);

temp = a[i];
a[i] = a[len-1];
a[len-1] = temp;
}
}
跟你的很象，会不会更好理解些？

2009-09-17 02:04 | mi

# re: 全排列算法原理和实现回复 更多评论

翟梦华同学认识错误，会c只是基础，算法可以是独立语言的一种思想，就像你会加减乘除，并不代表你会解物理题一样

2009-09-21 15:35 | 夏亮

# re: 全排列算法原理和实现回复 更多评论

mi同学的算法跟作者有什么不一样吗？

2009-09-21 15:36 | 夏亮

# re: 全排列算法原理和实现回复 更多评论

看看这个,这是后来写的,简单点了.

#include<iostream>

void contrary(char w[],int i){
for(int x=0;x<i/2;x++)
{char z=w[x]; w[x]=w[i-1-x]; w[i-1-x]=z;}
}

void permutation(char w[],int z){
if(z<2) return;
permutation(w,z-1);
contrary(w,z-1);
for(int i=0;i<z-1;i++){
for(int j=z-1;j>0;j--)
{char z=w[j]; w[j]=w[j-1]; w[j-1]=z;}
std::cout<<w;
permutation(w,z-1);
if(i<z-2) contrary(w,z-1);
}
}

int main(){
char w[]="ABCDE";
permutation(w,5);
system("pause");
}

我理解中算法就是算法嘛,就像数学本身是数学,不是微积分,线性代数的集合一样.

2010-04-30 23:12 | 翟梦华

# re: 全排列算法原理和实现[未登录] 回复 更多评论

你那个M传来传去的到底有什么用处啊

2010-05-21 21:10 | 李哲

# re: 全排列算法原理和实现回复 更多评论

算法有些细节需要优化。

比如你用if(k > m) 如果 k>m 需要转跳2此才可以返回函数

还有交换2个数2次，其实可以用局部变量来保存。

还有就是函数的参数传递~，可以考虑用全局函数保存指针

#include <iostream>

using namespace std;

int s[]={1, 2, 3, 4, 5, 6, 7, 8, 9};
const int N = sizeof(s)/sizeof(int);
int num;

void p(void);
void fun(int i);

int main(int argc, char *argv[])
{
fun(0);

cout << num << endl;
return 0;
}

inline void p(void)
{
for (int i=0; i < N; ++i)
{
cout << s[i] << " ";
}

cout << endl;
}

void fun(int i)
{
if (i == N)
{
// p();
++num;
return;
}

for (int a=i; a < N; ++a)
{
int x = s[i];
int y = s[a];

s[i] = y;
s[a] = x;
fun(i+1);
s[i] = x;
s[a] = y;

}

}

2010-08-10 21:50 | xk8

# re: 全排列算法原理和实现 回复 更多评论

其实昨天上面这个，没多少优化。

今天有做了个循环版的。。

结果简单的时间计算。

排列9位，运行100次
楼主的代码 9秒左右
翟梦华的代码 7-8秒左右
我的这个因为没有用递归只要3.5秒这样

#include <iostream>

using namespace std;

int s[] = {1,2,3,4,5,6,7,8,9};
const int N = sizeof(s)/sizeof(int);
int t[N];
int num;
void p(void);
void f(void);
void swap(int *a, int *b);

int main(int argc, char *argv[])
{

for (int a=0; a < 100; ++a)
f();

cout << num << endl;
return 0;
}

void f()
{
int a=0;

while(a != -1)
{
if (a == N)
{
//p();
a--;
num++;
}
else
{
while (a+t[a] == N)
{
t[a] = 0;
a--;
}

if (a != -1)
{

if (a != a+t[a])
{
swap(&s[a], &s[a+t[a]-1]);
}

swap(&s[a], &s[a+t[a]]);

t[a]++;

a++;
}

}
}
}

void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void p()
{
for (int i=0; i < N; ++i)
{
cout << s[i] << " ";
}

cout << endl;
}

2010-08-11 12:28 | 来着

新用户注册刷新评论列表


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 Chat2DB C++博客博问管理
相关文章: Twitter算法面试题详解（Java实现）百度面试题：求绝对值最小的数不使用中间变量交换两个数（Java版）有道难题2009复赛题解答（Java版）：求大于给定数的最小不重复数生成n*n蛇形矩阵的算法 Base64编码原理与实现 09考研数据结构试题的一种解法（Java版）选择排序(selection sort)算法实现希尔排序(shellsort)算法实现快速排序(quicksort)算法实现

李宁的极客世界