Module: Enumerable

Defined in:

lib/tsplab.rb

Overview

Enumerable

The code for the Traveling Salesman lab (tsplab.rb) extends the Enumerable module with a method that generates all permutations of a string, array, or any other object from a class the includes the Enumerable interface.

Instance Method Summary

• #each_permutation ⇒ Object

  Iterate over all possible permutations of the objects in this container.

Instance Method Details

#each_permutation ⇒ Object

Iterate over all possible permutations of the objects in this container. The permutations are generated in lexicographic order.

Example:

>> s = "ABCD"
=> "ABCD"
>> s.each_permutation { |x| p x }
"ABCD"
"ABDC"
"ACBD"
"ACDB"
"ADBC"
...
"DBCA"
"DCAB"
"DCBA"
=> nil

# File 'lib/tsplab.rb', line 1277

def each_permutation
  p = self.clone
  n = p.length
  res = []
  loop do
    if block_given?
      yield p
    else
      res << p.clone
    end
    # find largest j s.t. path[j] < path[j+1]
    j = n-2
    while j >= 0
      break if p[j] < p[j+1]
      j -= 1
    end
    break if j < 0
    # find largest i s.t. path[j] < path[i]
    i = n-1
    loop do
      break if p[j] < p[i]
      i -= 1
    end
    # exchange path[j], path[i]
    p[j], p[i] = p[i], p[j]
    # reverse path from j+1 to end
    tmp = p.slice!(j+1, n-1)
    p += tmp.reverse
  end
  return block_given? ? nil : res
end