c语言输出数组的全排列组合,定义一个数组，编程打印它的全排列

定义一个数组&＃xff0c;编程打印它的全排列。比如定义&＃xff1a;

#define N 3

int a[N] &＃61; { 1, 2, 3 };

则运行结果是&＃xff1a;

$ ./a.out

1 2 3

1 3 2

2 1 3

2 3 1

3 2 1

3 1 2

1 2 3

程序的主要思路是&＃xff1a;

把第1个数换到最前面来(本来就在最前面)&＃xff0c;准备打印1xx&＃xff0c;再对后两个数2和3做全排列。

把第2个数换到最前面来&＃xff0c;准备打印2xx&＃xff0c;再对后两个数1和3做全排列。

把第3个数换到最前面来&＃xff0c;准备打印3xx&＃xff0c;再对后两个数1和2做全排列。

可见这是一个递归的过程&＃xff0c;把对整个序列做全排列的问题归结为对它的子序列做全排列的问题

解题过程&＃xff1a;

(1) 当 N &＃61; 1的时候&＃xff0c;则直接打印数列即可。

(2) 当 N &＃61; 2的时候&＃xff0c;设数组为 [1, 2]

打印a[0], a[1] (即1&＃xff0c;2)

交换a[0],a[1]里面的内容

打印a[0],a[1]   (此时已变成了 [2, 1] )

(3) 当 N &＃61; 3的时候&＃xff0c;数组为 [1, 2, 3]

a.把1放在 a[0] 的位置(原本也是如此&＃xff0c;a[0] &＃61; a[0])&＃xff0c;打印2,3的全排列(即a[1], a[2]的全排列)

1  2  3

1  3  2b.  把2放在a[0]的位置(这时候需要交换原数组的a[0]和a[1])&＃xff0c;然后打印1, 3的全排列

2   1  3

2   3  1

打印完后再换回原来的位置&＃xff0c;即1还是恢复到a[0]&＃xff0c;2还恢复到a[1]的位置

c.把3放在a[0]的位置 (这时候需要交换的是原数组的a[0]和a[2])&＃xff0c;然后打印1, 2的全排列

3   2  1

3   1  2

打印完后再换回原来的位置&＃xff0c;即1还是恢复到a[0]&＃xff0c;3还恢复到a[2]的位置,

至此全排列完成

(4)N &＃xff1d; 4, 5, 6....的思路与此相同

点击(此处)折叠或打开

#include

#define N 3

int a[N];

void perm(int); /*求数组的全排列 */

void print();

void swap(int, int);//交换前缀

int main(){

int i&＃xff1b;

for(i &＃61; 0; i

a[i] &＃61; i &＃43; 1;

}

perm(0);

}

void perm(int offset){

int i, temp;

if(offset &＃61;&＃61; N-1){

print();

return;

}else{

for(i &＃61; offset;i

swap(i, offset);//交换前缀

perm(offset &＃43; 1);//递归

swap(i, offset);//将前缀换回来&＃xff0c;继续做前一次排列

}

}

}

void print(){

int i;

for(i &＃61; 0; i

printf(" %d ",a[i]);

printf("/n");

}

void swap(int i, int offset){

int temp;

temp &＃61; a[offset];

a[offset] &＃61; a[i];

a[i] &＃61; temp;

}

完成了上述要求之后再考虑第二个问题&＃xff1a;如果再定义一个常量M表示从N个数中取几个数做排列(N &＃61;&＃61; M时表示全排列)&＃xff0c;原来的程序照如下方式修改&＃xff1a;

点击(此处)折叠或打开

#include

#include

#define N 4

#define M 3

int a[N]; /* N个数 */

int temp[M]; /* 从N个数中选出的M个数 */

void perm(int, int); /* 排列 */

void swap(int, int); /* 交换两个数 */

void print(); /* 打印 */

int main(){

int i;

int start &＃61; 0;//起始位置

int count &＃61; M;//排列到个数

for(i &＃61; 0; i

a[i] &＃61; i &＃43; 1;

}

perm(start, count);

}

void perm(int offset, int count){

int i;

if( count &＃61;&＃61; 0 ){

print();

return;

}else{

for(i &＃61; offset; i

temp[offset] &＃61; a[i];

swap(offset, i);

perm(offset&＃43;1, count-1);

swap(offset, i);

}

}

}

void swap (int offset, int i){

int another;

another &＃61; a[offset];

a[offset] &＃61; a[i];

a[i] &＃61; another;

}

void print(){

int i;

for(i &＃61; 0; i

printf(" %d ",temp[i]);

printf("/n");

}

最后再考虑第三个问题&＃xff1a;从N个数中取M个数做组合,

先看一个例子&＃xff1a;

C(5,3) &＃61; 10

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5

分析

1 | 2 3

1 | 2 4

1 | 2 5

1 | 3 4

1 | 3 5

1 | 4 5

------ C(4, 2)∵可以在{2, 3, 4, 5}中挑2个出来。

2 | 3 4

2 | 3 5

2 | 4 5

------ C(3, 2)∵可以在{3, 4, 5}中挑2个出来。

3 | 4 5

------ C(2, 2)∵只能在{4, 5}中挑2个出来。

这样就很容易写出递归算法来&＃xff1a;

点击(此处)折叠或打开

Algorithm combination(n, k, A[l..n&＃43;l-1])

if k &＃61; 0

print ary[1..k]

else

for i←1 to n-k&＃43;1

ary[index&＃43;&＃43;] &＃61; A[l&＃43;i-1]

combination(n-i, k-1, A[l&＃43;i..n&＃43;l-1])

--index

endfor

源代码如下&＃xff1a;

点击(此处)折叠或打开

#include

#include

#define N 4

#define M 3

int a[N]; /* N个数 */

int temp[M]; /* 从N个数中选出的M个数 */

int top;

void comb(int, int); /* 组合 */

void swap(int, int); /* 交换两个数 */

void print(); /* 打印 */

int main(){

int i;

int start &＃61; 0;//起始位置

int count &＃61; M;//排列到个数

for(i &＃61; 0; i

a[i] &＃61; i &＃43; 1;

}

comb(start, count);

}

void comb(int offset, int count){

int i;

if( count &＃61;&＃61; 0 ){

print();

return;

}else{

for(i &＃61; offset; i

temp[top&＃43;&＃43;] &＃61; a[i];

comb(i&＃43;1, count-1);

--top;

}

}

}

void print(){

int i;

for(i &＃61; 0; i

printf(" %d ",temp[i]);

printf("/n");

}