在做欧拉计划351题时,要用容斥定理求一个整数以内的各个质因数及其积的倍数的个数,需要用到各质因数的全组合,在mma中,求组合就是列举子集,所以寻找一个简便的方法。

以下算法来自《手写代码必备手册》
(soulmachine@gmail.com)
https://github.com/soulmachine/acm-cheat-sheet

1.增量构造法
2.位向量法
3.二进制法

完整代码

#include <cstdio>
void print_subset1(int *S, int n, int *P, int cur, int ed)
{
    for (int i = ed; i < n; i++)
    {
        //use S[i]
        P[cur] = S[i];
        for (int j = 0; j <= cur; j++) printf("%d ", P[j]);
        printf("\n");
        //don't use S[i]
        print_subset1(S, n, P, cur + 1, i + 1);
    }
}

void print_subset2(int *S, int n, char *B, int cur)
{
    if (cur == n)
    {
        for (int i = 0; i < n; i++) if (B[i]) printf("%d ", S[i]);
        printf("\n");
        return;
    }
    B[cur] = 1;
    print_subset2(S, n, B, cur + 1);
    B[cur] = 0;
    print_subset2(S, n, B, cur + 1);
}

void print_subset3(int *S, int n)
{
    for (int i = 1; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
            if (i & (1 << j)) printf("%d ", S[j]);
        printf("\n");
    }
}
int main()
{
    const int n=4;
    int S[n];
    int P[n];
    char B[n];

    for(int i = 0; i < n; i++) S[i]=i+1;
    print_subset1(S, n, P, 0, 0);
    putchar('\n');
    print_subset2(S, n, B, 0);
    putchar('\n');
    print_subset3(S, n);

    return 0;
}

输出

D:\>a
1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4

1 2 3 4
1 2 3
1 2 4
1 2
1 3 4
1 3
1 4
1
2 3 4
2 3
2 4
2
3 4
3
4


1
2
1 2
3
1 3
2 3
1 2 3
4
1 4
2 4
1 2 4
3 4
1 3 4
2 3 4
1 2 3 4

但这些方法不能按集合元素的个数输出,这用SQL是很容易做到的。

with t as(select level l from dual connect by level<=4),
p(lv,path,last)as(select 1,cast(l as varchar(20)),l from t
union all
select lv+1,path||' '||l,l from p,t
where l>last and lv<4)
select * from p;

   LV PATH                       LAST
----- -------------------- ----------
    1 1                             1
    1 2                             2
    1 3                             3
    1 4                             4
    2 1 2                           2
    2 1 3                           3
    2 1 4                           4
    2 2 3                           3
    2 2 4                           4
    2 3 4                           4
    3 1 2 3                         3
    3 1 2 4                         4
    3 1 3 4                         4
    3 2 3 4                         4
    4 1 2 3 4                       4

一个复杂的输出上述结果的程序

void my_subset4(int *S, const int n)
{
    int t[n+1]= {0};
    int out[1<<n][2]= {0}; //level,last elem
    int path[1<<n][n]= {0}; //set

    for(int i=1; i<=n; i++) t[i]=i; //init t
    int cnt=1;
    for(int i=1; i<=n; i++,cnt++) //first level
    {
        out[i][0]=1;  //lv == set.size
        out[i][1]=t[i]; //last
        path[i][0]=1;
        path[i][1]=t[i];
    }
    for(int lv=2,begin=1,end=cnt-1; lv<=n; lv++,begin=end+1,end=cnt-1) //level 2- n
    {
        for(int idx=begin; idx<=end; idx++) //out[idx]
            for(int i=1; i<=n; i++) //t[i]
                if(t[i]>out[idx][1])
                {
                    out[cnt][0]=lv;
                    out[cnt][1]=t[i];
                    path[cnt][0]=lv;
                    for(int j=1; j<lv; j++)
                        path[cnt][j]=path[idx][j];
                    path[cnt][lv]=t[i];
                    cnt++;
                }
    }
    for(int i=1; i<cnt; i++,puts(""))
        for(int j=1; j<=path[i][0]; j++)
            printf("%d ",path[i][j]);
}

第1层可以合并到循环,稍微简单些

void my_subset5(int *S, const int n)
{
    int t[n+1]= {0};
    int out[1<<n][2]= {0}; //level,last elem
    int path[1<<n][n]= {0}; //set

    for(int i=1; i<=n; i++) t[i]=i; //init t
    int cnt=1;

    for(int lv=1,begin=0,end=0; lv<=n; lv++,begin=end+1,end=cnt-1) //level 1- n
    {
        for(int idx=begin; idx<=end; idx++) //out[idx]
            for(int i=1; i<=n; i++) //t[i]
                if(t[i]>out[idx][1])
                {
                    //out[cnt][0]=lv;
                    out[cnt][1]=t[i];
                    path[cnt][0]=lv;
                    for(int j=1; j<lv; j++)
                        path[cnt][j]=path[idx][j];
                    path[cnt][lv]=t[i];
                    cnt++;
                }
    }
    for(int i=1; i<cnt; i++,puts(""))
        for(int j=1; j<=path[i][0]; j++)
            printf("%d ",path[i][j]);
}

再删除一个冗余的数组变量

void my_subset5(int *S, const int n)
{
    int t[n+1]= {0};
    int path[1<<n][n+1]= {0}; //set

    for(int i=1; i<=n; i++) t[i]=i; //init t
    int cnt=1;

    for(int lv=1,begin=0,end=0; lv<=n; lv++,begin=end+1,end=cnt-1) //level 1- n
    {
        for(int idx=begin; idx<=end; idx++) //prior level
            for(int i=1; i<=n; i++) //t[i]
                if(t[i]>path[idx][lv-1])//last elem
                {
                    path[cnt][0]=lv;
                    for(int j=1; j<lv; j++)
                        path[cnt][j]=path[idx][j];
                    path[cnt][lv]=t[i];
                    cnt++;
                }
    }
    for(int i=1; i<cnt; i++,puts(""))
        for(int j=1; j<=path[i][0]; j++)
            printf("%d ",path[i][j]);
}