Task Number Four

The next problem is this.  Given a list of numbers, you can concatenate them in various orders to make a larger number.  The problem is to work out the order for a given list of numbers that will give you the largest combined number.

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