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 enumerable object.

Instance Method Details

#each_permutation ⇒ Object

Iterate over all possible permutations of the objects in this enumerable object. The permutations are generated in lexicographic order. The new permutations are shallow copies of this object.

Example:

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

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

def each_permutation
  n = self.length
  p = Array(0..n-1)
  res = []
  loop do
    perm = self.clone
    for k in 0...n do
      perm[k] = self[p[k]]
    end
    if block_given?
      yield perm
    else
      res << perm
    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