Ruby implementation of std::next_permutation

next_permutation.rb

# encoding: utf-8
# reference: http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

def next_permutation a
  return a if a.length < 2

  found_k = -1

  for k in 0...(a.length-1)
    found_k = k if a[k] < a[k+1]
  end

  return a.reverse if found_k == -1

  found_l = -1
  for l in (found_k+1)...(a.length)
    found_l = l if a[found_k] < a[l]
  end

  if found_k < found_l
    a[found_k], a[found_l] = a[found_l], a[found_k]
  end

  a[(found_k+1)..-1] = a[(found_k+1)..-1].reverse
  a
end

def assertion expected, given
  print "E: #{expected.inspect} G: #{given.inspect} ... "
  raise StandardError.new("Invalid!") if expected != given
  puts "Passed"
end

if __FILE__ == $0
  assertion [], next_permutation([])
  assertion [1], next_permutation([1])
  assertion [1,2,4,3], next_permutation([1,2,3,4])
  assertion [1,3,2,4], next_permutation([1,2,4,3])
  assertion [1,4,2,3], next_permutation([1,3,4,2])
  assertion [1,4,3,2], next_permutation([1,4,2,3])
  assertion [2,1,3,4], next_permutation([1,4,3,2])
  puts "Stage1 Over"
  permutated_counter = 1
  initial = [1,2,3,4]
  ongoing = [1,2,3,4] 
  puts initial.inspect
  loop {
    ongoing = next_permutation(ongoing)
    puts "#{permutated_counter}: #{ongoing.inspect}"
    if ongoing == initial
      break
    elsif permutated_counter > 30
      raise StandardError.new("Out of expected value")
    else
      permutated_counter += 1
    end
  }
  assertion(24, permutated_counter)
  puts "Stage2 Over"
  puts "All test has finished."
end