Skip to content

Instantly share code, notes, and snippets.

@jsami
Last active May 21, 2017 13:47
Show Gist options
  • Save jsami/9033e8816f709657b0e33fdac508d7d2 to your computer and use it in GitHub Desktop.
Save jsami/9033e8816f709657b0e33fdac508d7d2 to your computer and use it in GitHub Desktop.
# Let's suppose that there is a method Set.pickOne()
# which picks randomly an element from a given set
# We also introduce Set.empty which is the neutral element for the union operation (+)
function power_set(items)
if items.empty
return Set.empty
set <- copy(items)
e <- set.pickOne()
ps <- power_set(set.remove(e))
ps <- ps + add(ps, e)
return ps
# Iterative add
# arguments:
# set_of_sets: a set of sets
# e: an element to be added to each set inside set_of_sets
function add(set_of_sets, e)
set <- copy(set_of_sets)
foreach subset in set
subset.add(e)
return set
# Recursive add: this suppose the existence of a constructor Set.new(element)
# to create a set with an initial element
function add(set_of_sets, e)
if set_of_sets.empty
return Set.empty
subsets <- copy(set_of_sets)
subset <- subsets.pickOne()
subsets.remove(subset)
subset.add(e)
return Set.new(subset) + add(subsets, e)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment