I have a set of elements and some arbitrary partitions of it.

I want to get a partition that divides the set in the least amount of subsets and "respects" the previous existing partitions. By respecting, I mean:

Let A and B be partitions of set X. Partition A respects B if, for every two elements of X, e and f, if e and f are not in the same subset of X according to partition B, they are also not in the same subset of X according to partition A.

Example:

Set is {1,2,3,4,5,6}

Partition1 is {{1,2,3}, {4,5,6}}

Partition2 is {{1,2}, {3,4}, {5,6}}

A partition that would respect Partition1 and Partition2 (and any other partition) is the "every element in its subset" {{1},{2},{3},{4},{5},{6}} partition. However, I want the partition with the least number of subsets, in this case {{1,2}, {3},{4}, {5,6}}.

Is there an algorithm for this problem? I have googled quite a bit, but couldn’t find anything, probably because I am not being able to describe it well. However, it sounds like a generic problem that should be common.

(another way to describe the problem from this Wikipedia article would be: “how to get the coarsest partition that is finer than a set of arbitrary partitions”)

https://en.wikipedia.org/wiki/Partition_of_a_set

CodePudding user response：

I'll call the partition we're looking for the answer.

We'll build the answer as follows:

1. Take any element not in the answer.
2. Take the intersection of the subset containing this element from each partition.
3. Add this subset to the answer.
4. Repeat.

We'll have to go through these steps once per subset in the answer. At the end, every element will be in a unique subset in the answer, and these will be as coarse as possible.

CodePudding user response：

Here is some working Python:

def partition_to_lookup(partition):
    which_partition = {}
    i = 0
    for part in partition:
        for x in part:
            which_partition[x] = i
        i  = 1
    return which_partition

def combine_partitions (partitions):
    lookups = [partition_to_lookup(partition) for partition in partitions]
    reverse_lookup = {}
    for x in lookups[0].keys():
        key = tuple((lookup[x] for lookup in lookups))
        if key in reverse_lookup:
            reverse_lookup[key].add(x)
        else:
            reverse_lookup[key] = {x}

    return list(reverse_lookup.values())

print(combine_partitions([[{1,2,3}, {4,5,6}], [{1,2}, {3,4}, {5,6}]]))

If N is the size of the universe, m is the number of partitions, and k the total number of all sets in all partitions, then this will be O(N*m k).