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

caseyh at istar.ca caseyh at istar.ca
Sun May 8 17:41:21 CEST 2011

```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

```