Function Repository Resource:

MaximalSubsets

Source Notebook

Prune non-maximal subsets from a list of subsets

Contributed by: Carl Woll

ResourceFunction["MaximalSubsets"][list]

prunes non-maximal subsets from the sets in list.

Details and Options

A non-maximal subset is a list which is completely contained in 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, c}, {a, b, d}, {d, e}, {d}, {a}, {a, b}, {f}};

Remove the non-maximal subsets {d}, {a}, and {a,b}:

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

Scope (2) 

MaximalSubsets can handle a large list of subsets:

In[3]:=
SeedRandom[1];
list = DeleteDuplicates[
   RandomSample[Range@200, #] & /@ RandomInteger[{1, 99}, 1000]];

The number of maximal subsets:

In[4]:=
ResourceFunction["MaximalSubsets"][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