19
\$\begingroup\$

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

\$\endgroup\$

11 Answers 11

7
\$\begingroup\$

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.
\$\endgroup\$
0
6
\$\begingroup\$

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>

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Neil
    Feb 12, 2016 at 21:41
  • \$\begingroup\$ @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... \$\endgroup\$
    – user81655
    Feb 12, 2016 at 21:45
5
\$\begingroup\$

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.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! This appears to be Python 2, so you don't need the int() around the input. Also, you can put the for loop's body on the same line as for.... \$\endgroup\$
    – Dennis
    Feb 12, 2016 at 1:00
4
\$\begingroup\$

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 jth item from the left to the jth 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.

\$\endgroup\$
2
  • \$\begingroup\$ You can save a couple of chars by doing the conditional as (i^min(i,n+~i)%-2)%n. \$\endgroup\$
    – xnor
    Feb 17, 2016 at 0:54
  • \$\begingroup\$ That's not only short but insanely clever. Thank you! \$\endgroup\$
    – Dennis
    Feb 17, 2016 at 2:20
2
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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))
\$\endgroup\$
1
  • \$\begingroup\$ def t(x,n):return sum((x[i]-x[i-1])**2for i in range(n)) uses the implicit wrap-around of negative indices and saves 4 bytes. I know, wasn't part of the competition. ;) \$\endgroup\$
    – justus
    Feb 14, 2016 at 14:38
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.