把 0~2^n-1 划分为若干组使得每组异或和为 0

把 $0\sim 2^n-1$ $(n\ge 2)$ 划分为若干组使得每组异或和为 0，最多分出多少组？

显然组数的上界是 $\lceil\frac{n}{3}\rceil$。

可以递归构造：

def gen(n):
    if n==2: return [(0,),(1,2,3)]
    if n==3: return [(0,),(1,2,3),(4,5,6,7)]
    s=gen(n-2)
    res=[(0,),(1,2,3)]
    for i in s:
        if len(i)==3:
            key=[0,2,3,1]
            for j in range(4):
                res.append((i[0]<<2|j,i[1]<<2|key[j],i[2]<<2|key[key[j]]))
        elif len(i)==4:
            t=2**(n-1)
            res.append((t,t+1,t+2,t+3))
            res.append((4,t+9,t+13))
            res.append((5,t+11,t+14))
            res.append((8,t+7,t+15))
            res.append((10,t+6,t+12))
            res.append((12,t+4,t+8))
            res.append((15,t+5,t+10))
    if ~n&1: return res
    res2=[]
    for i in res:
        if set(i)!={4,8,12} and set(i)!={5,10,15}:
            res2.append(i)
    return res2

日期： 2019-11-06

标签： 算法

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/271/ 查看。