My first thought was that this is easy - just sort the numbers into largest first and then join them together. This would work for say 31 41 59 - - join them in sorted order 59 41 31 and you get 594131 which is the largest possibility.

However this won't work even for the example on the page - 50, 2, 1, 9. Put them in increasing order and you get 50921 but the largest result possible is 95021.

So is there a way to work out the largest by allowing for the fact that the numbers are different lengths? I'm sure there is but I haven't got time to try to work that our now. The clock is supposed to be ticking...

Therefore perhaps the way to do this is to just blindly work out the whole list of permutations of the number list and then get the maximum.

OK so if I have a list of numbers, how do I list all permutations?

Pardon me if I switch language here...

So firstly if I want all permutations I want to start with each of the numbers in turn so I want to be able to

**rotate**my list:

rotate :: [Int] -> [Int]

rotate [] = []

rotate (x:xs) = xs ++ [x]

Now for example:-

*Main> rotate [50, 2, 1, 9]

[2,1,9,50]

So to get a list of all possible

**rotations**of one list:-

rotations :: [Int] -> [[Int]]

rotations ns = take (length ns) (iterate rotate ns)

The function

**iterate**produces a potentially infinite list of repeated calls of the same function:

**take**allows us to get only as much of this infinite list as we need, which here is the number of elements

in the list so each one comes to the front once.

And for this example:-

*Main> rotations [50, 2, 1, 9]

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

So er yes I want to rotate through the first number of the list and then combine each number with successive permutations of the remainder of the list. Thinking recursively you see.

So perhaps I want the

**heads**of the list and the

**tails**of the list as separate lists:-

heads :: [Int] -> [Int]

tails :: [Int] -> [[Int]]

heads ns = ns

tails ns = map tail (rotations ns)

*Main> heads [50, 2, 1, 9]

[50,2,1,9]

*Main> tails [50, 2, 1, 9]

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

## No comments:

## Post a Comment