2011-08-25 09:32:02Morris
[分析] 生成排列大車拼
生成排列固然簡單, 要怎麼作才算是有效率 ?
現在提供 3 種作法,
1. 傳統排列 (標準型DFS)
2. 快速排列 (剪枝型DFS, 目前"我做的之中"最快)
3. 內建排列 (就內建, 沒什麼好講的)
範例輸入 :
3
範例輸出 :
ABC
CB
BAC
CA
CAB
BA
//與之前相同部分, 不做輸出,
事實上是
ABC
ACB
BAC
BCA
CAB
CBA
//現在開始測試, 測試時間, 不包括輸出的部分, 因為輸出太浪費時間了
n = 9
1. 0.020000 s
2. 0.008000 s
3. 0.013000 s
n = 10
1. 0.215000 s
2. 0.079000 s
3. 0.129000 s
n = 11
1. 2.479000 s
2. 0.855000 s
3. 1.364000 s
n = 12
1. 32.271000 s
2. 10.195000 s
3. 16.292000 s
總結下, 內建沒比較快, 以下是三支程式碼的測試
1.傳統排序
#include<stdio.h>
#include<string.h>
#include<time.h>
int map[20][20] = {}, n;
char Way[20], Last[20], Used[20] = {};
void DFS(int now, int set) {
int a;
if(now == 0) {/*
for(a = 0; a < set; a++) {
if(Way[a]-1+'A' != Last[a])
Last[a] = Way[a]-1+'A', printf("%c", Last[a]);
}
puts("");*/
return;
}
for(a = 1; a <= n; a++)
if(Used[a] == 0) {
Used[a] = 1;
Way[set] = a;
DFS(now-1, set+1);
Used[a] = 0;
}
}
main() {
freopen("in.txt", "rt", stdin);
freopen("out.txt", "w+t", stdout);
clock_t st, ed;
st = clock();
while(scanf("%d", &n) == 1) {
DFS(n, 0);
}
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
return 0;
}
2.快速排序
#include<stdio.h>
#include<string.h>
#include<time.h>
int map[20][20] = {}, n;
char Way[20], Last[20];
int next[20];
void DFS(int now, int set) {
int a, pre = 0;
if(now == 0) {
/*for(a = 0; a < set; a++) {
if(Way[a]-1+'A' != Last[a])
Last[a] = Way[a]-1+'A', printf("%c", Last[a]);
}
puts("");*/
return;
}
for(a = next[0]; a; pre = a, a = next[a])
if(!map[a][set]){
next[pre] = next[a];
Way[set] = a;
DFS(now-1, set+1);
next[pre] = a;
}
}
main() {
freopen("in.txt", "rt", stdin);
freopen("out2.txt", "w+t", stdout);
clock_t st, ed;
st = clock();
int a, x;
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
next[a] = a+1;
memset(Last, 0, sizeof(Last));
memset(map, 0, sizeof(map));
/*for(a = 1; a <= n; a++) {
while(scanf("%d", &x) == 1 && x != 0)
map[a][x-1] = 1;
}*/
next[n] = 0;
DFS(n, 0);
}
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
return 0;
}
using namespace std;
main() {
int n;
freopen("in.txt", "rt", stdin);
freopen("out3.txt", "w+t", stdout);
clock_t st, ed;
st = clock();
while(scanf("%d", &n) == 1) {
int i;
char t[26]={};
for(i = 0; i < n; i++) t[i] = i+'A';
do {
/*for(i = 0; i < n; i++)
printf("%c",t[i]);
puts("");*/
} while(next_permutation(t,t+n));
}
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
return 0;
}
現在提供 3 種作法,
1. 傳統排列 (標準型DFS)
2. 快速排列 (剪枝型DFS, 目前"我做的之中"最快)
3. 內建排列 (就內建, 沒什麼好講的)
範例輸入 :
3
範例輸出 :
ABC
CB
BAC
CA
CAB
BA
//與之前相同部分, 不做輸出,
事實上是
ABC
ACB
BAC
BCA
CAB
CBA
//現在開始測試, 測試時間, 不包括輸出的部分, 因為輸出太浪費時間了
n = 9
1. 0.020000 s
2. 0.008000 s
3. 0.013000 s
n = 10
1. 0.215000 s
2. 0.079000 s
3. 0.129000 s
n = 11
1. 2.479000 s
2. 0.855000 s
3. 1.364000 s
n = 12
1. 32.271000 s
2. 10.195000 s
3. 16.292000 s
總結下, 內建沒比較快, 以下是三支程式碼的測試
1.傳統排序
#include<stdio.h>
#include<string.h>
#include<time.h>
int map[20][20] = {}, n;
char Way[20], Last[20], Used[20] = {};
void DFS(int now, int set) {
int a;
if(now == 0) {/*
for(a = 0; a < set; a++) {
if(Way[a]-1+'A' != Last[a])
Last[a] = Way[a]-1+'A', printf("%c", Last[a]);
}
puts("");*/
return;
}
for(a = 1; a <= n; a++)
if(Used[a] == 0) {
Used[a] = 1;
Way[set] = a;
DFS(now-1, set+1);
Used[a] = 0;
}
}
main() {
freopen("in.txt", "rt", stdin);
freopen("out.txt", "w+t", stdout);
clock_t st, ed;
st = clock();
while(scanf("%d", &n) == 1) {
DFS(n, 0);
}
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
return 0;
}
2.快速排序
#include<stdio.h>
#include<string.h>
#include<time.h>
int map[20][20] = {}, n;
char Way[20], Last[20];
int next[20];
void DFS(int now, int set) {
int a, pre = 0;
if(now == 0) {
/*for(a = 0; a < set; a++) {
if(Way[a]-1+'A' != Last[a])
Last[a] = Way[a]-1+'A', printf("%c", Last[a]);
}
puts("");*/
return;
}
for(a = next[0]; a; pre = a, a = next[a])
if(!map[a][set]){
next[pre] = next[a];
Way[set] = a;
DFS(now-1, set+1);
next[pre] = a;
}
}
main() {
freopen("in.txt", "rt", stdin);
freopen("out2.txt", "w+t", stdout);
clock_t st, ed;
st = clock();
int a, x;
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
next[a] = a+1;
memset(Last, 0, sizeof(Last));
memset(map, 0, sizeof(map));
/*for(a = 1; a <= n; a++) {
while(scanf("%d", &x) == 1 && x != 0)
map[a][x-1] = 1;
}*/
next[n] = 0;
DFS(n, 0);
}
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
return 0;
}
3.內建排序
#include <iostream>using namespace std;
main() {
int n;
freopen("in.txt", "rt", stdin);
freopen("out3.txt", "w+t", stdout);
clock_t st, ed;
st = clock();
while(scanf("%d", &n) == 1) {
int i;
char t[26]={};
for(i = 0; i < n; i++) t[i] = i+'A';
do {
/*for(i = 0; i < n; i++)
printf("%c",t[i]);
puts("");*/
} while(next_permutation(t,t+n));
}
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
return 0;
}