Function Repository Resource:

MinimalSubsets

Source Notebook

Prune non-minimal subsets from a list of subsets

Contributed by: Carl Woll

ResourceFunction["MinimalSubsets"][list]

prunes non-minimal subsets from the sets in list.

Details and Options

A non-minimal subset is a list which includes all elements from another subset.
The argument list should be a list of subsets, where each subset is a list of elements.

Examples

Basic Examples (2) 

Here is a list of sets:

In[1]:=
list = {{a, b}, {b, c}, {a, b, c}, {a, b, e}, {a, c, e}, {a, e, d, f}}
Out[1]=

Remove the non-minimal subsets, which are {a,b,c} and {a,b,e}:

In[2]:=
ResourceFunction["MinimalSubsets"][list]
Out[2]=

Scope (2) 

MinimalSubsets can handle a large list of subsets:

In[3]:=
SeedRandom[1]
list = Table[
   RandomSample[Range[4000], RandomInteger@{3, 4000}], {8000}];

The number of minimal subsets:

In[4]:=
ResourceFunction["MinimalSubsets"][list] // Length // AbsoluteTiming
Out[4]=

Publisher

Carl Woll

Version History

  • 1.0.0 – 18 October 2019

Related Resources

Author Notes

Uses Internal`ListMin, which is based on the BCL algorithm discussed here: https://dl.acm.org/citation.cfm?id=320196.

License Information