Introduction to Ruby - Computing a Power Set : An Example of Recursion

Computing a Power Set

# Using Recursion to Computer the Power Set of a given set # Power Set is the Set of All Subsets of a Set # If S = {x,y,z} # Power Set = {{},{x},{y},{z},{x,y},{y,z},{x,z},{x,y,z}}

# index spans from Zero to lengthOfTheElements-1

# We go through the elements from position 0 to last # At each element we have an option - either to include the element in a particular subset, or to drop the element from the subset # For an initial set of N elements -> The Power Set will have 2^N elements # Either we drop an element from the original set or we retain the element from the original set - 2 options

def powerSet(index,elements,current_subset) if index == elements.length puts current_subset.join(" ; ") else # Compute Subsets which don't include the element at the current Index powerSet(index+1,elements,current_subset) # Compute Subsets which DO include the element at the current Index powerSet(index+1,elements,current_subset +[elements[index]]) end end

# Lets try out this function on 2 sets ["X","Y","Z"] and ["A","B","C","D","E","F","G","H"] # We start from Index 0, initially we have nothing but an empty subset