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

## 0 Comments:

## Post a Comment

Note: Only a member of this blog may post a comment.