Project Euler Problem 24
Used the algorithm on Wikipedia at http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation. It’s a generic method that takes any arbitrary list and the desired permutation number k.
Problem Statement
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
require "fixnum.rb" # Fixnum.factorial
def permutation(k, list)
size = list.size
factorial = (size-1).factorial
result = []
while result.size != size
x = k / factorial
x -= 1 if (k % factorial).zero?
result << list.delete_at(x)
k = k % factorial
factorial = (list.size - 1).factorial
end
result
end
puts permutation(1000000, [0,1,2,3,4,5,6,7,8,9]).join
