一行代碼一行淚。。。手都被發熱的筆記本烤的不舒服了。。。。6個多小時過去鳥。。。終於粗來鳥。。。。
昨天同學問到一個排列組合的問題，本身不會很難，原題是固定輸入4個數字，例如1 2 3 4，輸出所有可能的排列組合
暴力的話應該不難的。代碼+debug，半個小時。
如果是輸入N個數字呢？
先說簡單的暴力方法，如果輸入4個數字，輸出所有的排列組合
代碼比較短，也比較簡單，所以數字常量什麼的表介意。。。。
/********************************************************************** code writer : EOF code date :2014.06.11 e-mail : [email protected] code purpose: just for fun... ************************************************************************/ #includevoid fun(void); int main() { fun(); return 0; } void fun(void) { int array[4]; int buffer[4]; int temp = 0; int circle_1 = 0; int circle_2 = 0; int circle_3 = 0; int circle_4 = 0; printf("Hey,guys! Please input four numbers\n"); //Input four number . for(temp = 0;temp < 4;temp++) { while(!scanf("%d",&array[temp])) for(temp = 0;temp < 4;temp++) { while(!scanf("%d",&array[temp])) { while(getchar() != '\n') { } printf("Input again and make sure the input data is right.\n"); } } for(circle_1 = 0;circle_1 < 4;circle_1++) { buffer[0] = array[circle_1]; for(circle_2 = 0;circle_2 < 4;circle_2++) { if(array[circle_2] != array[circle_1]) { buffer[1] = array[circle_2]; for(circle_3 = 0;circle_3 < 4;circle_3++) { if(array[circle_3] != array[circle_2] && array[circle_3] != array[circle_1]) { buffer[2] = array[circle_3]; for(circle_4 = 0;circle_4 < 4;circle_4++) { if(array[circle_4] != array[circle_3] && array[circle_4] != array[circle_2] && array[circle_4] != array[circle_1]) { buffer[3] = array[circle_4]; for(temp = 0;temp < 4;temp++) { printf("%d ",buffer[temp]); } printf("\n"); } } } } } } } }
可以看出這裡嵌套的for循環層數是取決於等待排列的數據的個數的，開銷相當的大。
如果輸入N個數字，輸出所有的排列組合，這種方法是不可行的。
測試結果：
ubuntu2@ubuntu:~/Desktop$ ./a.out
Hey,guys! Please input four numbers
1 2 3 4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
利用遞歸。。。。做出n的版本。
注釋還沒來得及寫,明天補上，先上demo
/**************************************************************** code writer : EOF code date : 2014.06.12 e-mail:[email protected] code purpose: It's a hard time to finished this program but everthing is Ok...It was here. Just change the macro ARRAYSIZE into the number of input variable.This program would process it and print out all combination of your input. ****************************************************************/ #include#define ARRAYSIZE 3 #define USED 1 #define UNUSED 0 struct location { int state[ARRAYSIZE]; }; int buffer[ARRAYSIZE]; int array[ARRAYSIZE]; int check(int depth,struct location current_state); void fun(void); int main() { fun(); return 0; } void fun(void) { int temp = 0; int buffer[ARRAYSIZE]; struct location initial_state; for(temp = 0;temp < ARRAYSIZE;temp++) { while(!scanf("%d",&array[temp])) { while(getchar() != '\n') { } printf("Input error\nPlease input agina!"); } } for(temp = 0;temp < ARRAYSIZE;temp++) { buffer[temp] = 0; initial_state.state[temp] = UNUSED; } printf("\n\n"); check(ARRAYSIZE-1,initial_state); } int check(int depth,struct location current_state) { int temp = 0; int foo = 0; int last_location = -1; if(depth > 0) { for(foo = 0;foo < ARRAYSIZE ;foo++) { for(temp = 0;temp < ARRAYSIZE ;temp++) { if(temp <= last_location) { continue; } if(current_state.state[temp] == UNUSED) { current_state.state[temp] = USED; last_location = temp; buffer[ARRAYSIZE-(depth+1)] = array[temp]; check(depth-1,current_state); current_state.state[last_location] = UNUSED;//clear used location and prepare for next depth. break; } } } } else if(depth == 0) { for(temp = 0;temp < ARRAYSIZE ;temp++) { if(current_state.state[temp] == UNUSED) { current_state.state[temp] = USED; last_location = temp; buffer[ARRAYSIZE-(depth+1)] = array[temp]; break; } } for(temp = 0;temp < ARRAYSIZE;temp++) { printf("%d ",buffer[temp]); } printf("\n"); } }
