集合的整数表示

有一类问题是需要表示包含N个索引数字集合S = {0,1，...,n-1}的某个子集，这种子集(假设有k个元素,k<=n)可以用一个整数表示：

SK = 2^a1 + 2^a2 +... + 2^ak

subs={a1,a2,...,ak}

SK是subs的整数表示,这种方法可以基于位操作快速的实现某些集合运算，在编程竞赛中常常用到。

1.判断某个索引数字i是否在集合里

2.吧数字i从集合中删除

3.增加数字i

4.求所有的子集

5.求所有含k个元素的子集

python source code：

#to encode a set into a integer will give a more concise representation of  a small set which only contains
#elements from range(0,n)

class IntegerEncodedSet(object):

    def __init__(self,num):
        self.n = num

    def setsize(self):
        l,r=0,31
        while r-l>1:
            e = (l+r)/2

            if (1 << e) == self.n:
                return e+1
            if (1<<e) < self.n:
                l = e
            else:
                r = e
        return r


    def contains(self, element):
        return  (self.n>>element & 1) == 1

    def add(self,element):
        self.n=self.n|(1<<element)

    def remove(self,element):
        self.n=self.n&~(1<<element)

    def allsubsets(self):
        allsubsetIntegers=[self.n]
        sub = (self.n -1)&self.n
        while sub!=self.n:
            allsubsetIntegers.append(sub)
            sub = (sub -1)&self.n
        return allsubsetIntegers


    def all_klength_subsets(self,k):
        if k>=self.n:
            return []
        m = (1<<k)-1
        k_length_subsets=[]
        n = self.setsize()

        while  ( m < (1<<n)):
            x = m & - m
            y = m + x
            m = ((m&~y)/x >> 1) | y  #lex order of binary format of encoded set
            if (m&self.n==m):
                k_length_subsets.append(m)

        return k_length_subsets