The Minimal Set of Multisets Abstract Data Type

Introduction

The Minimal Set of Multisets (MSM) is a data structure that represents a set of multisets. No multiset in a MSM is a subset of another multiset in the MSM. When you add a new multiset to a MSM, one of two things happens:

1. If the new multiset is a superset of an existing multiset, nothing happens and the MSM remains unchanged.
2. Otherwise, if the new multiset is not a superset of any existing multiset, it is added to the MSM. Then, any multiset that is a superset of the added multiset is removed from the MSM.

Example

Suppose we have a MSM with the following multisets:

{1: 1, 2: 1, 3: 2}
{1: 1, 2: 2, 4: 1}
{1: 1, 3: 1, 5: 1}

If we add the multiset {1: 3, 2: 3, 3: 1, 4: 1}, nothing happens and the MSM remains unchanged, because the new multiset is a superset of the second multiset.

If we add the multiset {1: 1, 2: 1, 6: 1}, it is added to the MSM:

{1: 1, 2: 1, 3: 2}
{1: 1, 2: 2, 4: 1}
{1: 1, 3: 1, 5: 1}
{1: 1, 2: 1, 6: 1}

If we add the multiset {1: 1, 2: 2}, it is added to the MSM, and all its supersets are removed:

{1: 1, 2: 1, 3: 2}
{1: 1, 3: 1, 5: 1}
{1: 1, 2: 1, 6: 1}
{1: 1, 2: 2}

If we add the multiset {1: 1, 2: 1}, it is added to the MSM, and all its supersets are removed:

{1: 1, 3: 1, 5: 1}
{1: 1, 2: 1}

Implementation

You can find the implementation of the MSM in the minimal_set_of_multisets.py file.

Nevertheless, the implementation is not optimized for performance. It is intended to be a reference implementation, because the performance of the MSM is not critical for the Commander Spellbook project. If you need a more performant implementation, you can use the reference implementation as a starting point and optimize it for your use case.

These are the papers/links to refer for the implementation of an optimized MSS (Minimal Set of Sets) data structure:

• Stack Overflow Question #1
• Article: "Data structure set-trie for storing and querying sets: Theoretical and empirical analysis"
• Article: "Index Data Structure for Fast Subset and Superset Queries"
• Stack Overflow Question #2
• Stack Overflow Question #3

These are the papers/links to refer for the implementation of an optimized MSM (Minimal Set of Multisets) data structure:

• Article: "Multiset-Trie Data Structure" on MDPI and on ResearchGate

---

Last update: August 11, 2024 12:55:09
Created: December 30, 2023 13:33:09

Authors: ldeluigi