Skip to content

Instantly share code, notes, and snippets.

@jg-you
Last active August 29, 2015 14:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jg-you/8c4decd9831544887d03 to your computer and use it in GitHub Desktop.
Save jg-you/8c4decd9831544887d03 to your computer and use it in GitHub Desktop.
Find all supersets of a collection
collection = [{1, 2, 3, 4, 5},
{1, 2},
{1, 2, 3, 4, 5, 6},
{3, 4, 8},
{3, 4, 11},
{3},
{3},
{12},
{1, 2, 3, 4, 5, 6},
{1, 2, 3, 4, 7, 9},
{1, 2, 3, 4, 5, 8},
{3, 5, 10}]
sizes = set()
for i in collection:
sizes.add(len(i))
sizes = sorted(sizes, reverse=True)
X = dict()
for s in sizes:
X[s] = []
for s in collection:
X[len(s)].append(s)
for reference_size in sizes:
for reference_set in X[reference_size]:
for s in sizes:
if s == reference_size:
X[s][:] = [x for x in X[s] if not x.issubset(reference_set)] +\
[reference_set]
if s < reference_size:
X[s][:] = [x for x in X[s] if not x.issubset(reference_set)]
updated_collection = []
for s in X:
updated_collection += X[s]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment