随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

全排列算法原理和实现

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

全排列是将一组数按一定顺序进行排列,如果这组数有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;     
    
*= *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[] = {12345};     
    perm(list, 
04);     
    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 银河使者 阅读(7415) 评论(11)  编辑  收藏 所属分类: algorithmC/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 | 来着

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


网站导航: