Maximise the squared difference

Question

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).

Answer 1

Jelly, 24 21 15 14 10 9 bytes

RUĖµ«/€ị"

To compute the total squared difference, append µ_ṙ1$²S to the code. Try it online!

Background

One way to generate a permutation with maximized squared difference is to take the integers 1 to n in ascending order, and swap the second from the left with the second from the right, the fourth from the left with the fourth from the right, and so forth until we meet in the middle.

For example, for n = 8, 9 we have

1 2 3 4 5 6 7 8        1 2 3 4 5 6 7 8 9
  ^   ^ ^   ^            ^   ^   ^   ^

(carets mark integers to be swapped), which results in

1 7 3 5 4 6 2 8        1 8 3 6 5 4 7 2 9

after swapping.

One way to achieve these swaps, independently of the parity of n, is as follows.

Start by writing the integers in ascending order and in descending order, one below the other.

1 2 3 4 5 6 7 8        1 2 3 4 5 6 7 8 9
8 7 6 5 4 3 2 1        9 8 7 6 5 4 3 2 1

For each pair of integers, compute the minimum of the pair. This gives the distance to the nearest edge, i.e., the index from the left or the right (whichever is lower).

1 2 3 4 5 6 7 8        1 2 3 4 5 6 7 8 9
8 7 6 5 4 3 2 1        9 8 7 6 5 4 3 2 1

1 2 3 4 4 3 2 1        1 2 3 4 5 4 3 2 1

If the minimum is odd, the integer should stay in its place, so we select the one from the first row; if it is even, the integers should be swapped, so we select the one from the second row.

1   3     6   8        1   3   5   7   9
  7   5 4   2            8   6   4   2

This is the desired output.

How it works

RUĖµ«/€ị"    Main link. Input: n

R            Range. Yields [1, ..., n].
 U           Upend. Yields [n, ..., 1].
  Ė          Enumerate. Yields p := [[1, n], [2, n-1], ... [n-1, 2], [n, 1]].

   µ         Begin a new, monadic chain. Argument: p
     /       Reduce...
      €        each pair of p...
    «          by minimum.
        "    For each minimum and the corresponding pair of p:
       ị       Select the element at that index.
            Indices are modular and 1-based in Jelly, so this selects the first
            element if the minimum is odd, and the second one if it is even.

Answer 2

JavaScript (ES6), 52 bytes

n=>[...Array(n)].map((_,i)=>(i<n/2|n%2)^i%2?i+1:n-i)

9 bytes saved thanks to @Neil!

Explanation

This approach determines the number that should be at index i with a length of n rather than concatenating the results to an array. This is based on the following observation (using n = 7 as an example):

• Start with the lowest number on the left and the highest on the right: [ 1, 7 ]
• Switch the order so the lowest is on the right and the highest is on the left, increment the lowest, decrement the highest, and place them in the middle of the array: [ 1, 6, 2, 7 ]
• Repeat until the highest and lowest converge: [ 1, 6, 3, 4, 5, 2, 7 ]

The higher and lower numbers can easily be expressed as n-i and i+1 respectively.

var solution =

n=>
  [...Array(n)] // create an array of length n
  .map((_,i)=>  // set each value of the array at index i
    (i<n/2      // if we're on the left side,
    |n%2)       // or we're on the right and n is odd, even i => lower, odd i => higher
    ^i%2?       // else even i => higher, odd i => lower
    i+1:n-i
  )

N = <input type="number" id="input" oninput="result.textContent=solution(+this.value)" />
<pre id="result"></pre>

Answer 3

Python2, 105 98 bytes

7 bytes saved thanks to the comment by @Dennis

n=input()
r=([],[n/2+1])[n%2]
for i in range(n/2,0,-1):k=[n+1-i];r=([i]+r+k,k+r+[i])[i%2]
print r

Edited version 58 bytes

lambda n:[(n-i-1,i)[(i+(n,1)[i<n/2])%2]for i in range(n)]

I already believed it should be possible to do it as a one-liner, but the logic was too complex for me. Seeing the JavaScript-answer by @user81655 and the lambda-notation in @Dennis Python-answer, I gave it new try.

The condition is equal to

if i < n/2:
    i%2 != n%2
else:
    (i+1)%2

Unfortunately all the transformation effort saves only one no byte compared to the direct translation (i<n/2or n%2)!=i%2 of the JavaScript-logic.

Answer 4

Python, 51 49 bytes

lambda n:[(i^min(i,~i%n)%-2)%n for i in range(n)]

Thanks to @xnor for golfing off 2 bytes!

Try it on Ideone.

How it works

If i is a number in [0, ..., n - 1], then ~i % n = -(i + 1) % n = -(i + 1) + n = (n - 1) - i, meaning that it maps 0 to n - 1, 1 to n - 2 and, in general, the j^th item from the left to the j^th from the right.

As explained in my Jelly answer, we can construct the output by peeking at the lower value among i and ~i % n, and pick i if it is even and ~i % n if it is odd. We achieve this as follows.

• If the minimum is even, min(i,~i%n)%-2 will yield 0, so XORing the result with i will yield i, and computing its residue modulo n will return i.

• If the minimum is odd, min(i,~i%n)%-2 will yield -1, so XORing the result with i will yield ~i, so the entire expression evaluates to ~i % n as desired.

Answer 5

PHP, 77 76 51 50 49 bytes

Uses ISO 8859-1 encoding.

Assembling the first half of the array like this:

• Odd numbers have their index value (1, 3, 5..)
• Even numbers have the value of N+1-index (9, 7, 5)
• This results in 1, 9, 3, 7, 5

As for the second half of the array, the outermost values add up to N+1, which means you can get the corresponding right value from N-[left value] where the left value is already known.

for(;$k=$argv[1]-$j++;)echo" ",min($j,$k)%2?$j:$k;

Run like this (this also shows the total squared difference) (-d added for aesthetics only):

php -d error_reporting=32757 -r 'for(;$k=$argv[1]-$j++;)echo~ß,$x[]=min($j,$k)%2?$j:$k;  for(;$c=$x[+$i++];)$b+=($c-($x[$i]?:$x[0]))**2;echo"\n$b\n";' 10

• Saved a byte by negating left/right condition so the second ternary can be nested without parentheses
• Saved 25 bytes by shamelessly implementing Dennis' algorithm
• Saved a byte by getting rid of the needed space after echo
• Saved a byte by using ~ß to yield a space.

Answer 6

Python 2, 100

I know there's already a python answer, but I think I may have done this differently.

n=input();a=n%2;b=n/2;x=[b+1,b+a][a:]
for i in range(b+a-1):f=1-i%2*2;x=[x[-1]-f]+x+[x[0]+f]
print x

And as an extra to test the total score:

def t(x,n):return sum((x[i]-x[(i+1)%n])**2for i in range(n))

Answer 7

CJam, 17 15 14 bytes

{,W%ee_::e<.=}

This is a function that pops an integer n from the stack and pushes a permutation of [0 … n-1] in return. The code uses the same approach as my Jelly answer.

Try it online!

How it works

,W%ee_::e<.=    Function body. Stack: N

,               Turn N into [0 ... N-1].
 W%             Reverse to push [N-1 ... 0].
   ee           Enumerate. This pushes [[0 N-1] [1 N-2] ... [N-2 1] [N-1 0]].
     _          Push a copy of the array of pairs.
      ::e<      Reduce each pair by minimum.
          .=    Vectorized selection.
                For the Ith minimum M, select the Mth element of the Ith pair.
                Indices are modular and 0-based in CJam, so this selects the first
                element if the minimum is even, and the second one if it is odd.

Answer 8

LISP, 86 bytes

(defun g(n m)(if(= n m)(list n)(if(< m n)(cons m(reverse(cons n(g(- n 1)(+ m 1))))))))

The inputs of the function allow to choose the start (m) and the end (n) values of the sequence.

For testing the function according to the provided samples, n is fixed to N and m to 1.

Here the code to test the function:

    (defun g(n m)(if(= n m)(list n)(if(< m n)(cons m(reverse(cons n(g(- n 1)(+ m 1))))))))

(defun sq (c)
    (apply #'+ (mapcar #'(lambda(x y) (* (- x y) (- x y))) c (append (cdr c) (list (car c))))))

(format t "N~20TSequence~50TSquared Difference~%")
(mapcar #'(lambda (x)(format t "~S~20T~S~50T~S~%" x (g x 1) (sq (g x 1)))) '(1 2 3 4 5 6 7 8 9 10 33 100 333 1000))

Try it on Ideone!

Answer 9

Julia, 39 bytes

n->map(i->min(i-1,n-i)%2>0?n-~-i:i,1:n)

This prints a permutation of 1:n. A permutation of 0:n-1 does neither cost nor save bytes:

n->map(i->min(i,n+~i)%2>0?i:n+~i,0:n-1)

This last version is a direct port of my Python answer.

Answer 10

R, 117 86 bytes

z=1:(n<-scan());a=pmin(z,n:1);for(i in seq(2,,2,n%/%2))z[b]=z[rev(b<-which(a==i,T))];z

edit replaced buggy long version with an implementation of @Dennis' Jelly algorithm

Answer 11

ES6, 77 bytes

n=>[...Array(n)].map(_=>r[++i&2?"push":"unshift"](i&1?n--:++j),i=j=0,r=[])&&r

The i&1 samples the digits from the extremes to the middle. The i&2 adds them to the beginning or end of the result in pairs.