Array#each_permutation

array_permutation_ext.rb

# Taken here http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/247669. Reformatted.
# based on the C++ standard library's implementation by Ken Bloom

class Array
  def next_permutation!
    return self if length<2
    i = length-1
    while true
      ii = i
      i -= 1
      if self[i] < self[ii]
        j = length
        nil until self[i] < self[j -= 1]
        self[i], self[j] = self[j], self[i]
        reverse_part!(ii, length)
        return self
      end
      if (i == 0)
        reverse!
        return self
      end
    end
  end

  def next_permutation
    dup.next_permutation!
  end

  def reverse_part! start,stop
    while start < stop
      self[start], self[stop-1] = self[stop-1], self[start]
      stop -= 1
      start += 1
    end
  end

  private :reverse_part!

  # each_permutation implementation that permutes based on
  # the contents of the array. No duplicate permutations are
  # yielded, even when there are duplicate elements in
  # the array. The elements of the array must
  # be mutually comparable. 
  def each_permutation
    temp = sort
    stop = temp.reverse
    yield temp
    until temp.next_permutation! == stop
      yield temp
    end
  end
end