评论
#re: 全排列算法原理和实现回复更多评论
#include
#include
#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
num[x]='A'+x;
Show();
for(int y=0;y
counter[y]=CHESSNUM-1;
Rank_Chess(CHESSNUM);
cout<
cout<
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
alter[i]=num[CHESSNUM-1-i];
for(int j=0;j
num[CHESSNUM-m+j]=alter[j];
Show();
}
/**********************************************************/
inline void Show(){
for(int x=0;x
cout<
cout<
num_counter++;
}
这是我以前写的,虽然长了点有点啰嗦,但我测试过了,对9位数排列比你的快了13s.不信你自己试试.但我得承认你的代码写得很棒!
-07-26 18:36 | 翟梦华
#re: 全排列算法原理和实现回复更多评论
哦,真是越看越惭愧,你的思路可要比我清晰多了。虽然大家用的都是递归之妙,但我写的东西真是太不成体统了。原本自己只学过2个礼拜的C便自以为已得算法之精妙,奈何山外有山。。。
-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
tmpString = preStrings[t];
for (int m =0 ;m
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
tmpString = preStrings[t];
for (int m =0 ;m
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
//tmpString = returnAll(n-1)[t];
for (int m =0 ;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
tmpStrings[i]=strings[i].toString();
}
return tmpStrings;
}
}
对于9位数的排列未打印用时1秒分左右。
-07-31 14:46 | fei
#re: 全排列算法原理和实现回复更多评论
#include
#include
#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
str[i]=str[i+1];
}
void qpl(int str[],int m,int n)
{
int i;
if(m==n+1)
{
for(i=1;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);
}
对楼主的算法的另一种表述
-05-04 14:33 | ~~
#re: 全排列算法原理和实现回复更多评论
#include
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
{
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;
}
}
跟你的很象,会不会更好理解些?
-09-17 02:04 | mi
#re: 全排列算法原理和实现回复更多评论
翟梦华同学认识错误,会c只是基础,算法可以是独立语言的一种思想,就像你会加减乘除,并不代表你会解物理题一样
-09-21 15:35 | 夏亮
#re: 全排列算法原理和实现回复更多评论
mi同学的算法跟作者有什么不一样吗?
-09-21 15:36 | 夏亮
#re: 全排列算法原理和实现回复更多评论
看看这个,这是后来写的,简单点了.
#include
void contrary(char w[],int i){
for(int x=0;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
for(int j=z-1;j>0;j--)
{char z=w[j]; w[j]=w[j-1]; w[j-1]=z;}
std::cout<
permutation(w,z-1);
if(i
}
}
int main(){
char w[]="ABCDE";
permutation(w,5);
system("pause");
}
我理解中算法就是算法嘛,就像数学本身是数学,不是微积分,线性代数的集合一样.
-04-30 23:12 | 翟梦华
#re: 全排列算法原理和实现[未登录]回复更多评论
你那个M传来传去的到底有什么用处啊
-05-21 21:10 | 李哲
#re: 全排列算法原理和实现回复更多评论
算法有些细节需要优化。
比如 你用if(k > m) 如果 k>m 需要转跳2此才可以返回函数
还有交换2个数2次, 其实可以用局部变量来保存。
还有就是 函数的参数传递~,可以考虑用全局函数保存指针
#include
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;
}
}
-08-10 21:50 | xk8
#re: 全排列算法原理和实现回复更多评论
其实昨天上面这个,没多少优化。
今天有做了个 循环版的。。
结果简单的时间计算。
排列9位,运行100次
楼主的代码 9秒左右
翟梦华的代码 7-8秒左右
我的这个因为没有用递归 只要3.5秒这样
#include
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;
}
-08-11 12:28 | 来着
如果觉得《全排列的java算法_全排列算法原理和实现》对你有帮助,请点赞、收藏,并留下你的观点哦!