[Haskell-cafe] For Project Euler #24 you don't need to generate all the lexicographic permutations <Spoiler>

[caseyh at istar.ca]

For Project Euler #24 you don't need to generate all the lexicographic  
permutations by Knuth's method or any other.

You're only looking for the millionth lexicographic permutation of  
"0123456789"


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?





<Spoiler>






<Spoiler>






<Spoiler>






Plan of attack:

-- The "x"s are different numbers
-- 0xxxxxxxxx represents 9! = 362880 permutations/numbers
-- 1xxxxxxxxx represents 9! = 362880 permutations/numbers
-- 2xxxxxxxxx represents 9! = 362880 permutations/numbers


-- 20xxxxxxxx represents 8! = 40320
-- 21xxxxxxxx represents 8! = 40320

-- 23xxxxxxxx represents 8! = 40320
-- 24xxxxxxxx represents 8! = 40320
-- 25xxxxxxxx represents 8! = 40320
-- 26xxxxxxxx represents 8! = 40320
-- 27xxxxxxxx represents 8! = 40320

etc.





<Spoiler>







<Spoiler>








-- lexOrder "0123456789" 1000000 ""

lexOrder digits left s
     | len == 0              = s ++ digits
     | quot > 0 && rem == 0  = lexOrder (digits\\(show  
(digits!!(quot-1))))  rem (s ++ [(digits!!(quot-1))])
     | quot == 0 && rem == 0 = lexOrder (digits\\(show (digits!!len)))  
       rem (s ++ [(digits!!len)])
     | rem == 0              = lexOrder (digits\\(show  
(digits!!(quot+1))))  rem (s ++ [(digits!!(quot+1))])
     | otherwise             = lexOrder (digits\\(show  
(digits!!(quot))))    rem (s ++ [(digits!!(quot))])
     where
     len = (length digits) - 1
     facLen = factorial len
     (quot,rem) = quotRem left facLen