组合与全排列非递归算法

组合与全排列非递归算法

二进制组合算法:
思路是开一个数组,其下标表示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

根据网上算法改编。

Leave a Reply

Your email address will not be published. Required fields are marked *