国产一区电影,男人的天堂在线免费视频,精品一区二区三区视频日产

全排列算法原理和實現

本文為原創，如需轉載，請注明作者和出處，謝謝！

全排列是將一組數按一定順序進行排列，如果這組數有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 銀河使者閱讀(7879) 評論(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)算法實現

李寧的極客世界

全排列算法原理和實現

《Android開發完全講義（第2版）》（本書版權已輸出到臺灣）

《Android高薪之路：Android程序員面試寶典 》http://book.360buy.com/10970314.html

評論

# re: 全排列算法原理和實現 回復 更多評論

# re: 全排列算法原理和實現 回復 更多評論

# re: 全排列算法原理和實現 回復 更多評論

# re: 全排列算法原理和實現 回復 更多評論

# re: 全排列算法原理和實現 回復 更多評論

# re: 全排列算法原理和實現 回復 更多評論

# re: 全排列算法原理和實現 回復 更多評論

# re: 全排列算法原理和實現 回復 更多評論

# re: 全排列算法原理和實現[未登錄] 回復 更多評論

# re: 全排列算法原理和實現 回復 更多評論

# re: 全排列算法原理和實現 回復 更多評論

導航

公告

常用鏈接

留言簿(126)

我參與的團隊

隨筆分類(818)

隨筆檔案(310)

文章分類(1)

文章檔案(8)

相冊

ADSL、3G查詢

CSDN

eclipse

ibm

Java EE

Linux

Web

云服務

代理網站

關注的網站

協議

喜歡的Blog

國內廣告平臺

圖書出版

在線培訓

開發工具

微博客戶端

手機鈴聲

操作系統

數學

文件格式

源碼資源

移動（Mobile）

編程語言

英語學習

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

《Android高薪之路：Android程序員面試寶典》http://book.360buy.com/10970314.html

# re: 全排列算法原理和實現回復更多評論

# re: 全排列算法原理和實現回復更多評論

# re: 全排列算法原理和實現回復更多評論

# re: 全排列算法原理和實現回復更多評論

# re: 全排列算法原理和實現回復更多評論

# re: 全排列算法原理和實現回復更多評論

# re: 全排列算法原理和實現回復更多評論

# re: 全排列算法原理和實現回復更多評論

# re: 全排列算法原理和實現[未登錄] 回復更多評論

# re: 全排列算法原理和實現回復更多評論

# re: 全排列算法原理和實現回復更多評論