19
1
Consider a permutation of the integer values from 1
to N
. E.g. this example for N = 4
:
[1, 3, 4, 2]
We'll consider this list to be cyclic, such that 1
and 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 0
to N-1
instead of 1
to N
.
Standard code-golf rules apply.
Test Data
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
:
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).
Nice algorithm; I tried and failed to think of a formula to generate them so I had to use the uglier method of pushing and unshifting. However, I can of course simplify your logic to
(i<n/2||n%2)^i%2?i+1:n-i
. – Neil – 2016-02-12T21:41:47.200@Neil Wow, I just woke up, decided to golf this and came up with your exact logic and started typing it out right as you posted it! Crazy... – user81655 – 2016-02-12T21:45:11.563