Problem 24

Projekt Euler w Ruby
1

Problem 24

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?

2

Ruby >= 1.8.7

(0..9).to_a.permutation.take(1_000_000).last.join
3

To rozwiazanie jest jednak znacznie szybsze:

#!/usr/bin/env ruby n = 1000000-1 t = (0..9).to_a s = "" f = (1..9).inject(1) { |f, i| f*i } 9.step(0, -1).each do |i| s << t.delete_at(n/f).to_s n %= f f /= (i == 0 ? 1 : i) end p s.to_i