CODEWITHSUNDEEP
algorithmdata-structuresset
gurditsbedi
gurditsbedi

Reputation: 69

Maximizing a boolean function of AND and XOR on paritions of set

Given a set of distinct positive integers S we need to partition a set in such a way that the following function is maximize. Let S1, S2, ... Sn be the parition. n can be atleast 2.

F(S1, S2, ..., Sn) = AND(XOR(S1), XOR(S2), ..., XOR(Sn))) where, AND is bitwise AND operation and XOR is bitwise XOR operation

We need to print the all such partitions possible.

I have tried the exponential approach as shown below. I am looking for a solution with lesser complexity.

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

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}')

INPUT: the set itself OUTPUT: max value possible followed by the all the partitions producing it

INPUT: 

[2, 3, 4]

OUTPUT: 

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

INPUT: 

[2, 4, 6, 8]

OUTPUT: 

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]]

Upvotes: 2

Views: 150

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

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

Hint: if we consider each bit separately from the highest to lowest, we can consider bit k as being set in the result if and only if that bit can appear an odd number of times in each part of the partition.

Upvotes: 0

Related Questions