algorithm practice: permutations (using lexical successor to generate)

permutations.rb

require 'pp'

def succ(a)
  # destructive to a
  n = a.size
  k = (n-2).downto(0) do |k|
    break k if a[k] < a[k+1]
  end
  return nil if a[k] >= a[k+1]
  l = (n-1).downto(0) do |l|
    break l if a[k] < a[l]
  end
  a[k], a[l] = a[l], a[k]
  a[k+1..-1] = a[k+1..-1].reverse
  a
end

def assert_succ(a, b)
  if succ(a) != b
    pp a
    pp b
    pp succ(a)
    raise 'error'
  end
end

assert_succ([0,1,2,3], [0,1,3,2])
assert_succ([0,1,3,2], [0,2,1,3])

x = [0,1,2,3,4,5]
i = 0
while x do
  i += 1
  pp x
  x = succ(x)
end
puts "#{i} found"