enumerate subset

| 分类 trick  | 标签 trick 

生成集合的所有子集

基于2进制的方法

一开始2B的我直接想到是模拟2进制加法,一点一点加上去。这种方法在数据小的情况下速度是优良的,但稍大一点可能就吃不消了。而且在这个模拟的进程中,剪枝有一些限制,不能剪得彻底。

当需要有规律的2进制生成时,一个广为人知的code就是Gray code。它是以前用来发现数据错误的,其具有2个相邻子集只相差1个元素的性质。其实只要具有这种性质,都可以称之为Gray code。例如有2位2进制数,最具有美感的Gray code的生成方式为:

G(x) = x ^ (x » 1), 其中^为异或操作,»是右移操作,它来源于对n维正方体的顶点用Gray code进制编码。以4位2进制数为例。

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

for (int i = 0; i < (1 << 4); ++i)
    g = i ^ (i >> 1);

不过还一种方法,它按照选中的个数增加的方式来生成2进制数。称为banker’s sequence。 这里先坑着,面包会有的。。。

这里再来一个比较风骚的写法。假设共有10个物品,枚举则可以这样写。

int S = (1 << 10) - 1;
for (int i = S; i; i = (i - 1) & S)
    // do sth...

就这样是看不出来优点的,如果你已经把某些不可能的情况可剪枝掉了,即0b1110011111是全部的情况。只要将上面的S改变一下就行了。

基于数组的方法

向量的方式,比2进制的方法速度慢,只是它可以所针对的长度远高于2进制数的表示范围。 一般的构造方式都是这样:

void subset(int a[], int cur, int n)
{
    if (cur == n) {
        // do sth...
        return;
    }

    a[cur] = 0;
    subset(a, cur + 1, n);

    a[cur] = 1;
    subset(a, cur + 1, n);
}

或许你看到了这个尾递归,想把它给优化掉,不过一般现在的C/C++编译器都支持尾递归优化了(-O2)。

上面这种方法是间接的通过一个数组来决定是否选择了元素。

还有一种比较特殊的情况,就是你要枚举的对象具有先后顺序、可比较的性质。故可以采用基于字典序来生成。例如你要枚举0 1 2这3个数的选中情况,直接对它们进行选取,不必应用中间数组。

主要思想就是:在当前的状态下选择1个比前1个元素刚刚大的元素,选择它,然后就遇到了相同的问题了,则显然递归。

以数字的来举例。

void subset(int a[], int cur, int limit)
{
    // todo sth. print `array a', etc...

    int s = cur > 0 ? a[cur - 1] + 1: 0;
    for (int i = s; i < limit; ++i) {
        a[cur] = i;
        subset(a, cur + 1, limit)
    }
}

程序显得相当的简洁。:)

并且这个算法产生的序列是lexicographic,如果在每一个subset操作前都打印一下数组a,则显示的内容具有 ‘empty 0 01 012 02 1 12 2’ 的形式。

看到了这个序列中相同长度的串从左到右都是递增的(这不是废话嘛?从subset中就可以看出来了)。如果从整个序列中拿出来,就可以更加明显地显示出它的特点。

以2位的为例:’01 02 12’,这就好比是1个{A, B, C}3个数的集合先出现了前2位,再出现了前后2位,最后产生后2位。如果把完整的2进制形式写出来,显得更加明显了。

‘110’ ‘101’ ‘011’,这就是一步一步把1向右推进嘛。即此刻我们正在enumerate。并且enumerate的2进制形式中1的个数都是一样的。其实啊,这就是banker’s sequence.只要将subset稍候改写一下,即可生成这些2进制序列。

int length = 4;// the size of set

void output(int a[], int limit)
{
    int order[length];

    memset(order, 0, sizeof(order));
    for (int i = 0; i < limit; ++i)
        order[a[i]] = 1;
    for (int i = 0; i < length; ++i)
        cout << order[i];
    cout << endl;
}

void subset(int a[], int cur, int limit)
{
    if (cur == limit) {
        output(a, limit);
        return;
    }

    int start = cur > 0 ? a[cur - 1] + 1 : 0;
    for (int i = start; i < length; ++i) {
        a[cur] = i;
        subset(a, cur + 1, limit);
    }
}

int main()
{
    int a[length];
    for (int i = 0; i <= length; ++i)
        subset(a, 0, i);

    return 0;
}

The End.

总结

其实banker sequence与lexicographic sequence都是用了一个思想,把要enumerate的对象的位置给找到了,只不过banker sequence多了一步转换的过程。

参考

http://www.applied-math.org/subset.pdf


上一篇     下一篇