euler24.rb

   1 require 'logger'
   2 $log = Logger.new(STDERR)
   3 $log.level = Logger::WARN
   4
   5
   6 class Integer
   7   def to_factorial_radix
   8     return [0] if self == 0
   9     remainder = self
  10     result = []
  11     radix = 1
  12     while remainder > 0
  13       result << (remainder % radix)
  14       remainder = remainder.div radix
  15       radix += 1
  16     end
  17     result.reverse
  18   end
  19 end
  20
  21 class Array
  22   def factorial_radix_to_i(current_radix = 0)
  23     $log.info { "Calling factorial_radix_to_i with string #{self} and current_radix = #{current_radix}" }
  24     return 0 if self.empty?
  25     return 0 if self == [0]
  26     value_of_rest = self[0..-2].factorial_radix_to_i(current_radix + 1)
  27     $log.info { "Value of remainder = #{value_of_rest}" }
  28     $log.info { "Returning #{self[-1] + value_of_rest}" }
  29     self[-1] + (current_radix + 1) * value_of_rest
  30   end
  31
  32   def prepad_with_zeros(length)
  33     [0] * [length - self.length, 0].max + self
  34   end
  35
  36   def permutation_from_factorial_radix_number(n)
  37     $log.info { "Permuting #{self} with frn #{n}" }
  38     return [] if n.empty?
  39     return self if self.empty?
  40     items_copy = self.dup
  41     permutation = [items_copy.delete_at(n[0])]
  42     permutation += items_copy.permutation_from_factorial_radix_number(n[1..-1])
  43   end
  44
  45   def nth_permutation(n)
  46     permutation_from_factorial_radix_number(n.to_factorial_radix.prepad_with_zeros(self.length))
  47   end
  48 end
  49
  50 if __FILE__==$0
  51   puts (Array.new(10) {|i| i}).nth_permutation(10 ** 6 - 1).join('')
  52 end
  53
  54 $log.close