Puzzle

[sobrique]

I have a minor problem to solve.

Due to a problem where my Dad works, he needs to figure out how to sort some numbers.
But they need to be sorted such that there is more than 2 between each number in the sequence.

eg. 2, 4, 6, 8 would become 4, 8, 2, 6.

The problem is in figuring out the 'best' sort algorithm to do this programatically.
Oh and ideally using every frequency.

(The background is that the numbers represent 'channel numbers' on a radio system, and they're separated by 50Mhz. If they're less than 2 apart, then there's interference)

There's probably a beer (or other drink of choice) in it for anyone who can give me a good solution.

Comments

[ewx.livejournal.com]

Your example suggests you mean "at least 2" rather than "a minimum of 2" - is that right?

[sobrique.livejournal.com]

errm. Yeah.
More than 2. (I've modified the post a little to clarify)

[ewx.livejournal.com]

In retrospect my question was as poorly phrased as your original description, with less excuse l-) I was thinking about the problem a bit at lunchtime but didn't come up with any answers. (Clearly you can do it in O(n.n!) steps by checking every possible order, but presumably you'd like to do better than that...)

[darkgodfred.livejournal.com]

Hmmm. I'm not certain if this'll work since I've thought about it for maybe five minutes, still...

First, sort the list in ascending order, standard problem. Hack the list into two equal lists, a one of big numbers and a one of small numbers. Keep them sorted. Then just read alternate numbers off the two lists.

That'll run into problems if the number spread isn't sufficently broad, but if that's the case then you're probably screwed anyway.

And an example.

7,3,6,5,9,1,8,2,10,4 => 1,2,3,4,5,6,7,8,9,10 => 1,2,3,4,5 | 6,7,8,9,10

=> 1,6, 2,7, 3,8, 4,9, 5,10

And one where it fails

1,2,3,6 => 1,2 | 3,6 => 1,3,2,6

Now, find yourself a mathematician to prove that it works.

Tristan

[darkgodfred.livejournal.com]

On further thought it'll work as long as less than half the list within the same 2-wide patch of the number line.