PHPFixing
  • Privacy Policy
  • TOS
  • Ask Question
  • Contact Us
  • Home
  • PHP
  • Programming
  • SQL Injection
  • Web3.0

Monday, November 7, 2022

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

 November 07, 2022     algorithm, partitioning, set     No comments   

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)
  • Share This:  
  •  Facebook
  •  Twitter
  •  Stumble
  •  Digg
Newer Post Older Post Home

0 Comments:

Post a Comment

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

Total Pageviews

Featured Post

Why Learn PHP Programming

Why Learn PHP Programming A widely-used open source scripting language PHP is one of the most popular programming languages in the world. It...

Subscribe To

Posts
Atom
Posts
Comments
Atom
Comments

Copyright © PHPFixing