algorithm - 在集合的分区上最大化 AND 和 XOR 的 bool 函数

Question

给定一组不同的正整数 S，我们需要 partition以下列函数最大化的方式设置。设 S₁, S₂, ... S_n 为分区。 n 至少可以为 2。

F(S₁, S₂, ..., S_n) = AND(XOR(S₁), XOR(S₂), ..., XOR(S_n))) 其中，AND为按位与运算，XOR为按位异或运算

我们需要打印所有可能的分区。

我尝试了如下所示的指数方法。 我正在寻找复杂性较低的解决方案。

这个问题是家庭作业的一部分，所以只提供提示。

from functools import reduce
from collections import defaultdict

def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset
        yield [ [ first ] ] + smaller
        # print("END OF THE LOOP")


x = 4
initialAssum = [2, 4, 8, 16]
something = initialAssum

def andxor(xs):
    def xorlist(xs):
        return reduce(lambda i, j: i ^ j, xs)

    tmp = [xorlist(x) for x in xs]

    return reduce(lambda i, j: i & j, tmp)

ans = defaultdict(list)
for n, p in enumerate(partition(something), 1):
    r = andxor(p)
    if len(p) > 1:
        ans[r].append(p)

m = max(ans.keys())
for a in ans[m]:
    print(a)
    #print(a, len(a))
print(f'{m}')

输入:集合本身 输出:可能的最大值，然后是产生它的所有分区

输入:

[2, 3, 4]  

输出:

2  
[[4, 2], [3]]  
[[2], [4, 3]]  

输入:

[2, 4, 6, 8]

输出:

0   
[[2], [4, 8, 16]]  
[[2, 4], [8, 16]]  
[[4], [2, 8, 16]]  
[[2], [4], [8, 16]]  
[[2, 4, 8], [16]]  
[[4, 8], [2, 16]]  
[[2], [4, 8], [16]]  
[[2, 8], [4, 16]]  
[[8], [2, 4, 16]]  
[[2], [8], [4, 16]]  
[[2, 4], [8], [16]]  
[[4], [2, 8], [16]]  
[[4], [8], [2, 16]]  
[[2], [4], [8], [16]]

Answer 1

This problem is part of a homework, so only provide the hint.

提示:如果我们从最高到最低分别考虑每个位，当且仅当该位在每个位中出现奇数次时，我们可以认为位 k 被设置在结果中分区的一部分。