输入N个数，输出所有可能的排列组合
一行代码一行泪。。。手都被发热的笔记本烤的不舒服了。。。。6个多小时过去鸟。。。终于粗来鸟。。。。
昨天同学问到一个排列组合的问题，本身不会很难，原题是固定输入4个数字，例如1 2 3 4，输出所有可能的排列组合
暴力的话应该不难的。代码+debug，半个小时。
如果是输入N个数字呢？
先说简单的暴力方法，如果输入4个数字，输出所有的排列组合
代码比较短，也比较简单，所以数字常量什么的表介意。。。。
/**********************************************************************
code writer : EOF
code date :2014.06.11
e-mail : jasonleaster@gmail.com
code purpose:
just for fun...
************************************************************************/
#include
void 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:jasonleaster@gmail.com
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");
}
}
