输出一组数字的所有排列

kampoo 发表于 2005-12-29 14:29

输出一组数字的所有排列，最简单的算法是什么？

fewrains 发表于 2006-1-1 13:15

递归,从VChelp的算法版主那里抄来的:
 #define N_permutation 5 // 排列元素数量
unsigned char flag; // 标记元素是否被使用 unsigned char dat; // 记录临时元素队列 unsigned char p_dat=0; // 对列指针
void out_dat() // 输出对列dat中的内容 { for(int i=0;i<N_permutation;i++) cout<<dat<<' '; cout<<endl; }
void permutation() // 再入函数，生成N_permutation个字母的所有排列, { // 最大递归次数为N_permutation unsigned char i; // 被再入函数入栈保护的局部变量 for(i=0;i<N_permutation;i++) { if (flag==0) { flag=1; // 标记元素被使用 dat=0x41+i; // 将字母添加到队列 p_dat++; 
 if (p_dat==N_permutation) // 对列满输出， out_dat(); else permutation(); // 否则继续添加 p_dat--; flag=0; } } } void main() { permutation(); getch(); }

fewrains 发表于 2006-1-1 13:16

前头要加上:
#include <iostream> #include <conio.h> using namespace std;

fewrains 发表于 2006-1-3 00:44

非递归实现，效率不错
#include <iostream> #include <conio.h> #include <windows.h> using namespace std;
void output(int *p); //输出函数 void permutation(int *p);//全排列函数
int a[]={1,2,3,4,5,6,7,8,9,10,11};//待排列数组 int N=sizeof(a)/sizeof(int); //数组长度 int *p=a; //数组指针
void main() { permutation(p); //调用全排列函数 output(p); //输出排列结果 getch(); }
void permutation(int *p) { bool flag=false; //标志排列是否结束 int temp; //临时变量,用来交换数组元素
 while(1) { for(int i=0;i<N-1;i++) { flag=true; //如已排列完,falg为真
 if(p<p) //如果发现第一个倒序的数组元素,p被称为倒序元素 { flag=false; //说明未排列完
 int j=0; while(p>=p); //找到第一个大于或等于倒序元素的数组元素 j-=1; 
 temp=p; //交换这两个元素 p=p; p=temp;
 j=0; while(j<(i+1)/2) //倒置倒充元素原位置以前的所有元素 { temp=p; p=p; p=temp; j++; } break; //跳出for循环, } } if(flag) //如果排列完,结束循环 break; //output(p); //输出排列结果 } }
void output(int *p) { cout<<endl; for(int i=0;i<N;i++) cout<<p<<' ';
}

dsg333 发表于 2006-2-19 05:16

还有吗？

zhouming09 发表于 2006-3-6 17:01

太高深了不东

zansan 发表于 2006-5-7 19:49

递归容易明白,就是慢,这个算法就是好.找到"倒置位"后进行倒置.

jinfly4997 发表于 2006-8-11 20:22

matlab里面好像有这个函数，我用过，但现在实在是既不起来了，你可以寻求帮助,但如果英语不太好，建议买一本参考教材看看相关命令，或者上网查一些有关命令的资料下载就是了，我的大部分matlab知识就是寻求网上帮助获得的，你也可以试试！

sjian2001 发表于 2006-10-21 22:16

看过一篇文章是这么说的： 比如说求1，2，3的全排列， 先是{ 1 } 然后用2，在元素里所有空当插入 变成了{ 21 , 12} 然后用3，在元素里所有空当插入 {321,231,213,312,132,123} 算法还是好实现的。 不知道跟其他算法有什么效率差别。

页: [1]

数学建模社区-数学中国's Archiver

输出一组数字的所有排列