permutations :: (Eq a) => [a] -> [[a]]

permutations [] = [[]]

permutations xs = [ h:t | h <- xs, t <- permutations (xs `except` h) ]

*Main> permutations "HORSE"

["HORSE","HORES","HOSRE","HOSER","HOERS","HOESR",

"HROSE","HROES","HRSOE","HRSEO","HREOS","HRESO",

"HSORE","HSOER","HSROE","HSREO","HSEOR","HSERO",

"HEORS","HEOSR","HEROS","HERSO","HESOR","HESRO",

"OHRSE","OHRES","OHSRE","OHSER","OHERS","OHESR",

"ORHSE","ORHES","ORSHE","ORSEH","OREHS","ORESH",

"OSHRE","OSHER","OSRHE","OSREH","OSEHR","OSERH",

"OEHRS","OEHSR","OERHS","OERSH","OESHR","OESRH",

"RHOSE","RHOES","RHSOE","RHSEO","RHEOS","RHESO",

"ROHSE","ROHES","ROSHE","ROSEH","ROEHS","ROESH",

"RSHOE","RSHEO","RSOHE","RSOEH","RSEHO","RSEOH",

"REHOS","REHSO","REOHS","REOSH","RESHO","RESOH",

"SHORE","SHOER","SHROE","SHREO","SHEOR","SHERO",

"SOHRE","SOHER","SORHE","SOREH","SOEHR","SOERH",

"SRHOE","SRHEO","SROHE","SROEH","SREHO","SREOH",

"SEHOR","SEHRO","SEOHR","SEORH","SERHO","SEROH",

"EHORS","EHOSR","EHROS","EHRSO","EHSOR","EHSRO",

"EOHRS","EOHSR","EORHS","EORSH","EOSHR","EOSRH",

"ERHOS","ERHSO","EROHS","EROSH","ERSHO","ERSOH",

"ESHOR","ESHRO","ESOHR","ESORH","ESRHO","ESROH"]

*Main> length (permutations "HORSE")

120

*Main> 5 * 4 * 3 * 2 * 1

120

*Main>

That's more like it.

Slipped the factorial in there just for fun: 120 permutations.

Now given a list of integers I want the value of the concatenation of their string representations: build this up...

*Main> let ns = [50, 2, 1, 9]

Convert each integer in the list into the string form, with function

**show**:-

*Main> map show ns

["50","2","1","9"]

Now concatenate the whole list by

**folding**the binary

**concatenation**operator

**++**into the list with

**""**as the base case:-

*Main> foldr (++) "" (map show ns)

"50129"

Now

**read**this to get the integer value:

*Main> read (foldr (++) "" (map show ns))

No instance for (Read a0) arising from a use of `read'

Aha, need to help

**read**by specifying the destination type:

*Main> read (foldl (++) "" (map show ns)) :: Int

50219

So wrap this in a nice function:-

value :: [Int] -> Int

value ns = read (foldl (++) "" (map show ns)) :: Int

Right. So I can now generate all the permutations and assign a single value to each one. Finally I need the maximum value from the list. Aha, there is already a function

**maximum**that does this.

*Main> maximum (map value (permutations [50, 2, 1, 9]))

95021

QED (Quite Easily Done)

I haven't been keeping track but that definitely was more than an hour.

On reviewing the solution posted by the original blogger I see he went down the track of comparing strings, and spotted that the problem is made hard by the fact that the numbers can be represented by strings of different lengths.

I like this Haskell solution because you read that last line of code and it pretty much tells you what it does.

## No comments:

## Post a Comment