Consider a permutation of the integer values from
N. E.g. this example for
N = 4:
[1, 3, 4, 2]
We'll consider this list to be cyclic, such that
2 are treated as adjacent. One quantity we can compute for such a list is the total squared difference of adjacent values:
(1-3)² + (3-4)² + (4-2)² + (2-1)² = 10
Your task is to find a permutation which maximises this quantity, given a positive integer
N. In the case of
N = 4 the above example is not optimal (in fact, it's minimal). We can achieve a total squared difference of
18 with the following permutation (as well as several others):
[1, 4, 2, 3]
Your algorithm must run in polynomial time (of
N). In particular, you cannot simply compute the total squared difference of all permutations.
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.
Output may be in any convenient, unambiguous, flat list or string format. You may choose to return a list with values from
N-1 instead of
Standard code-golf rules apply.
There is a nice analytical solution for this problem. E.g. all valid solutions for
N = 10 are equivalent to the following list (up to cyclic shifts and reversal):
[7, 5, 6, 4, 8, 2, 10, 1, 9, 3]
I don't want to reveal too much beyond that (although it's probably enough to figure out the pattern), so instead of giving any more examples, you can check that your results have the following total squared differences for a given
N Total squared difference 1 0 2 2 3 6 4 18 5 36 6 66 7 106 8 162 9 232 10 322 33 11936 100 333202 333 12308236 1000 333332002
This is OEIS entry A064842 (which also contains a reference to a paper with a solution to this challenge if you're stuck).