Introduction to Ruby

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

powerSet(0,["X","Y","Z"],[])
powerSet(0,["A","B","C","D","E","F","G","H"],[])

Sample Output:

~/work/ruby_tutorials$ ruby powerSet.rb

Z
Y
Y ; Z
X
X ; Z
X ; Y
X ; Y ; Z

Next one is much bigger :

H
G
G ; H
F
F ; H
F ; G
F ; G ; H
E
E ; H
E ; G
E ; G ; H
E ; F
E ; F ; H
E ; F ; G
E ; F ; G ; H
D
D ; H
D ; G
D ; G ; H
D ; F
D ; F ; H
D ; F ; G
D ; F ; G ; H
D ; E
D ; E ; H
D ; E ; G
D ; E ; G ; H
D ; E ; F
D ; E ; F ; H
D ; E ; F ; G
D ; E ; F ; G ; H
..........................................................

Check out some of our other Ruby Tutorials :

Introduction to Ruby and some playing around with the Interactive Ruby Shell (irb) Introduction to Ruby - Conditional statements and Modifiers: If-then, Unless, Case Introduction to Ruby Comments - Single and Multi-Line comments Introduction to Ruby Loops - Using While, Until, For, Break, Next , Redo, Retry
Introduction to Ruby - Arrays - Sorting, Filtering (Select), Transforming, Multi-Dimensional Arrays Introduction to Ruby - Strings Introduction to Ruby - Making a Script Executable Introduction to Ruby - Regular Expressions, Match, Scan
Introduction to Ruby - Computing Factorials Recursively : An Example of Recursion Introduction to Ruby - Binomial Coefficients (nCr) : An Example of Recursion Introduction to Ruby - Computing a Power Set : An Example of Recursion Introduction to Ruby - Towers of Hanoi : An Example of Recursion
Introduction to Ruby - Strings: Substitution, Encoding, Built-In Methods

Basic Data Structures With Ruby

Basic Data Structures in Ruby - Insertion Sort Basic Data Structures in Ruby - Selection Sort Basic Data Structures in Ruby - Merge Sort Basic Data Structures in Ruby - Quick Sort Functional Programming with Ruby
Basic Data Structures in Ruby - Stack Basic Data Structures in Ruby - The Queue Basic Data Structures in Ruby - Linked List - ( A Simple, Singly Linked List) Basic Data Structures in Ruby - Binary Search Tree