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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
