class Permuter

Permuter.rb

Encapsulates the logic of creating permutations

Usage:
 p = Permuter.new
 p.add_array [0,1]
 p.add_array [0,1]
 p.permutations
 => ["00","01","10","11"]

Methods:
 #add_array arr
 #permutations

 #any?
 #empty?
 #clear

Test Suite:

Complete

Public Class Methods

new() click to toggle source
# File lib/permuter.rb, line 26
def initialize
  @arrays = []
end

Public Instance Methods

add_array(arr) click to toggle source

Add an array to be permuted Raises an error if given nil

# File lib/permuter.rb, line 32
def add_array arr
  raise "Cannot add nil array" if arr == nil
  @arrays << arr
end
any?() click to toggle source
# File lib/permuter.rb, line 42
def any?
  @arrays.any?
end
clear() click to toggle source

Remove all arrays

# File lib/permuter.rb, line 38
def clear
  @arrays = []
end
empty?() click to toggle source
# File lib/permuter.rb, line 46
def empty?
  @arrays.empty?
end
permutations() click to toggle source

Get all permutations of the previously registered arrays Returns an array of strings, or an empty array if none were registered

# File lib/permuter.rb, line 53
def permutations
  return [] if @arrays.empty?
  @permutations = []
  permute []
  @permutations
end

Private Instance Methods

build_permutation(indices) click to toggle source
# File lib/permuter.rb, line 88
def build_permutation indices
  permutation = []
  indices.each_with_index do |item_code,i|
    permutation << @arrays[i][item_code]
  end
  result = permutation.join('')
  @permutations << result
  result
end
permute(indices) click to toggle source

permute (indices) Recursively generate every permutation of the arrays (Courtesy of Ari Fordsham)

The classic recursive permutation algorithm: Imagine picking a combination lock: [0][0] Each cylinder is the index to one of the arrays On each recursion, we add another cylinder [0], [0], [0][0] When we have enough cylinders, we generate the permutation (base case) and iterate to the next value by dropping a cylinder, [0] iterating the loop in else, and recursing again [0][1] Simple and elegant

# File lib/permuter.rb, line 72
def permute indices
  # Base case
  # puts "permute(#{indices})"
  if indices.length == @arrays.length # If the set of indices is complete
    # Build a `String` based on the completed set of indices
    build_permutation indices
  else
    # Otherwise, add a cylinder, iterate through its options;
    # If it's the final cylinder it will trigger the base case on every option and return;
    # If it's not, it will also trigger this case and iterate through the options of the next cylinder.
    @arrays[indices.length].each_with_index do |item,i|
      permute indices.dup << i
    end
  end
end