I could see that this problem was solvable by hand, but that’s no fun.

Instead I decided to implement it with a tree. Not the most efficient solution to be certain, especially the way I rolled it, but it was a fun exercise. I don’t get to play with trees often enough.

Problem #24

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

def nth_lexical_permutation values, key = "", chain = ""

  chain    = chain + key.to_s
  children = values.select { |i| i != key }

  $count -= 1 if children.size == 0
  return chain if $count == 0

  children.each do |i|
    result = nth_lexical_permutation children, i, chain
    return result if result.size > 0
  end
  ""
end

$count = 1_000_000
set    = (0..9).to_a

puts nth_lexical_permutation(set)

Yep, there’s a global in there. It just made things easier. There are actually quite a few things I don’t like about this program. But it’s late. And I’m tired.