组合生成算法

作者在 2010-10-01 14:04:17 发布以下内容
#include<iostream>
using namespace std;
void print(const int A[], const int B[], int Bn)
{
    for (int i = 0; i != Bn; ++i)
        cout << A[*(B+i)];
}

bool fun(int B[], int Bn, int An)//处理进位
{
    int x = Bn-1;
    while(B[x] > x+An-Bn)
    {
        if(x == 0) return false;
        B[x-1] += 1;
        --x;
    }
    while(x != Bn-1)
    {
        B[x+1] = B[x]+1;
        ++x;
    }
    return true;
}

void C(const int A[],int An, int Bn)//C(An,Bn),数组A[]是元素的集合
{
    if (Bn == 0 || Bn > An) //C(An,Bn) 0 < Bn <= An
    {
        cerr << "error";
        return;
    }
    int *B = new int[Bn];
    for (int i = 0; i != Bn; ++i)
        B[i] = i;
    int j = 0;
    while(fun(B,Bn,An))
    {
        print(A, B, Bn);
        cout << ',';
        if (j++ == 5)
        {
            cout << endl;
            j= 0;
        }
        ++B[Bn-1];
    }
    delete []B;
}
int main()
{
    int A[] = {1,2,3,4,5,6,7};
    int n;
    while(cin >> n)
    {
        system("cls");
        C(A,sizeof(A)/sizeof(int),n);
    }
    return 0;
}

关键思想是,采取一种类似十进制进位的处理方式。

数组B[]里储存的是下标。用来引索A[]。

B[x]的取值范围为[B[x-1]+1, A.length-B.length+x];//x>0

当B[x] == A.leng-B.length+x+1时发生进位 //循环处理进位

B[y]发生进位,B[y-1]没有发生进位则重新定位B[y]到B[Bn-1]的值。B[y] =B[y-1]+1,

当B[0]>A.length-B.length时算法结束

默认分类 | 阅读 1486 次
文章评论,共1条
tanghf1014
2010-10-17 09:44
1
看不懂////
游客请输入验证码
浏览30047次