组合与全排列非递归算法
二进制组合算法:
思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标
代表的数被选中,为0则没选中。
首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为
“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得
到了最后一个组合。
例如求5中选3的组合:
1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5
全排列N进制算法:
从1到N,输出全排列,共N!条。
分析:用N进制的方法。设一个N个单元的数组a用来存放待全排列的数组的下标,对第一个单元做加一操作,满N进一。每加一次一就判断一下各位数组单元有无重复,有则再转回去做加一操作,没有(且数组a中没有值为N的元素)则说明得到了一个排列方案。
例如:求1-3的全排列,共3!条
设数组初始状态为0 0 0,以下为计算全排列的步骤:
0 0 0 +1
1 0 0 +1
2 0 0 +1
3 0 0 满3进1 ->
0 1 0 +1
1 1 0 +1
2 1 0 +1
3 1 0 满3进1 ->
0 2 0 +1
1 2 0 +1
2 2 0 +1
3 2 0 满3进1 ->
0 3 0 满3进1 ->
0 0 1 +1
1 0 1 +1
2 0 1 +1
3 0 1 满3进1 ->
0 1 1 +1
1 1 1 +1
2 1 1 +1
3 1 1 满3进1 ->
0 2 1 +1
1 2 1 +1
2 2 1 +1
3 2 1 满3进1 ->
0 3 1 满3进1 ->
0 0 2 +1
1 0 2 +1
2 0 2 +1
3 0 2 满3进1 ->
0 1 2 +1
1 1 2 +1
2 1 2 +1
3 1 2 满3进1 ->
0 2 2 +1
1 2 2 +1
2 2 2 +1
3 2 2 满3进1 ->
0 3 2 满3进1 ->
0 0 3 满3进1 -> (最高位为进制n(这里是3)是循环退出条件)
0 0 0
其中用红色背景色表明的6个下标序列是合格的,每一个下标序列对应一种排列。
实现代码:
#include
#include
#define N 5
void Combine(int *a, int n);
void Arrange(int *a, int n);
bool CheckSame(int *a,int n);
void main(void)
{
int a[N] = {0, 1, 2, 3, 4};
int nType;
while (1) {
printf("1.组合\n");
printf("2.排列\n");
printf("0.退出\n");
printf("请选择 : ");
scanf("%d", &nType);
switch (nType) {
case 1: Combine(a, N); break;
case 2: Arrange(a, N); break;
case 0: return;
}
printf("\n");
}
}
void Combine(int *a, int n)
{
int i, j, k, m;
//
printf("选取个数 : ");
scanf("%d", &m);
if ((m > n) || (m < 1)) {
printf("选取范围[1, %d]\n", n);
return;
}
//
int *b = new int[n];
memset(b, 0, n*sizeof(int));
for(i = 0; i < m; i++) {
b[i] = 1;
}
int nCount = 0; bool bFound = false;
do {
for (i = 0; i < n; i++) {
if (b[i] == 1) {
printf("%d ", a[i]);
}
}
nCount++;
printf("\n");
bFound = false;
for (i = 0; i < n - 1; i++) {
if ((b[i] == 1) && (b[i+1] == 0) && (b[0] != 0)) {
b[i] = 0; b[i+1] = 1;
bFound = true;
break;
}
else if ((b[i] == 1) && (b[i+1] == 0) && (b[0] == 0)){
b[i] = 0; b[i+1] = 1;
bFound = true;
k = 0;
for (j = 0; j < i; j++) {
if (b[j] == 1) {
k++;
}
}
for(j = 0; j < i; j++) {
if (j < k) {
b[j] = 1;
}
else {
b[j] = 0;
}
}
break;
}
}
} while (bFound == true);
printf("Total number is : %d\n", nCount);
delete []b; b = NULL;
}
void Arrange(int *a, int n)
{
int *b = new int[n]; //数组b用来存下标
for(int i=0;i
根据网上算法改编。