[FIXED] How to get the partition with the least number of subsets that respects other partitions?

Issue

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

Solution

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).

Answered By - btilly

Answer Checked By - Cary Denson (PHPFixing Admin)