Code golf the best permutation

Question

Challenge

Given an integer n ≥ 4, output a permutation of the integers [0, n-1] with the property that no two consecutive integers are next to each other. The value of a permutation pi is the sum of abs(pi[i] - i) for all indices i.

Examples

• (1, 3, 0, 2) has value 6
• (0, 2, 4, 1, 3) has value 6
• (0, 2, 4, 1, 3, 5) has value 6
• (0, 2, 4, 1, 5, 3, 6) has value 8

Score of your answer

The score of your answer is the sum of the values of your permutations for n = 4 .. 14 plus the number of bytes your code takes. The lower the score, the better. Your code must give valid output for all those values of n.

You must be able to run your submission to completion on your machine.

In case of ties, time of last edit that resulted in the relevant score will be the decider.

Isn't this the same question as this one?

Answers to the linked question will not be competitive for this question as they make no effort to optimize the value of a permutation. For example for n=10, the permutation [1, 3, 5, 7, 9, 0, 2, 4, 6, 8] given by most of the answers there gives a value of 30. You can do much better than that.

For the permutation part of the question, the optimal value overall is at most 120. (Thank you to @Laikoni.) Whereas Dennis's answer to the previous question scores 222. (Thank you to @user202729.)

Answer 1

Jelly, 36 34 33 32 31 30 bytes, result: 120

Thanks to Dennis for -1 byte! (implicitly by fixing a Jelly bug, although the feature postdates the challenge)

ðRḟISị“Ƥ¿‘Ʋœ?$;@µ2x5~4¦ṁ_4$Ä’

New feature: accumulated sum (Ä).

Try it online!

Use 1-indexing.

Takes linear time, too.

---

This C++ program generates the lexicographically smallest permutation, assuming that |i - p_i| ≤ width (where width is a hardcoded constant) for all 0 ≤ i < n, with time complexity about O(width² × 2^2×width × n) (which is just O(n) for fixed width): Try it online!

---

How?

1. Write a C++ program attempting to solve the problem optimally.

2. Observe the pattern. We note that the sequence of all elements except 4 last ones is a prefix of

   0 2 4 1 3 5 7 9 6 8 10 12 14 11 13 15 17 19 16 18 20 22 24 21 23 25 ...
   

3. Computes the sequence's incremental difference.

   2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2
   

   Note the period 5.

4. The Jelly implementation:

   • n-4 first elements are taken from the sequence above. O(n).

   • For 4 last elements, just brute force all 24 possibilities. O(1).

     (note: I no longer brute force all 24 possibilities from the 32-bytes version)

Answer 2

CJam (60 bytes + 120 = 180 score)

{_5/4*8e!961=7_)er<:A\,^e!{A\+}%{2ew::-:z1&!},{_$.-:z1b}$0=}

Online test suite with integrated scoring

Extension up to n=24

Dissection

{
  _5/4*        e# Work out how much of the hard-coded prefix to use
  8e!961=7_)er e# Prefix [0 2 4 1 3 5 8 6]
               e# I identified this by brute forcing up to n=10 and looking for patterns
               e# I then used the identified prefix [0 2 4 1] to brute-force further
  <:A          e# Take the desired prefix of the hard-coded array, and store a copy in A
  \,^e!        e# Generate all permutations of the values in [0 .. n-1] which aren't in A
  {A\+}%       e# Prepend A to each of them
  {            e# Filter...
    2ew::-     e#   Take each difference of two consecutive elements
    :z         e#   Find their absolute values
    1&         e#   Test whether 1 is among those absolute values
    !          e#   Reject if it is
  },
  {            e# Sort by...
    _$.-       e#   Take pairwise differences of permutation with the identity
    :z         e#   Absolute values
    1b         e#   Add them (by interpreting in base 1)
  }$
  0=           e# Take the first
}

Answer 3

Haskell, 146+89 score+bytes

f i|k<-mod i 4=scanl(+)1$take(i-2-k)(cycle[2,-3,2,3])++[[2],[2,2],[5,-3,2],[5,-3,2,2]]!!k

Repeats pattern [1,3,0,2], last mod i 4 elements are hand tuned.

Previous algorithm (132+116):

f i=last$filter(\a->all(`elem`a)[0..i-1]).(!!(i-1)).iterate((\l->map((:l).(+head l))[-3,2,-2,3])=<<)$pure<$>[i-3..i]

Bruteforces the correct number of jumps of length ±2 or ±3. Selects the last one that has the correct numbers in it, seems to work just fine and is a lot cheaper than implementing the score. Tio just runs out time before the last score, which is 18.

Try it online!

Answer 4

Japt, 120 + 20 = 140

(Copying one of my solutions from the other challenge would have scored me 227)

o á k_äa d¥1ÃñxÈaYÃg

Try it or use this version to check scores. Both versions may start crapping out on you around 9.

---

Explanation

o                        :Range [0,input)
  á                      :All permutations
    k_      Ã            :Remove sub-arrays that return true
      äa                 :  Get the consecutive absolute differnces
         d¥1             :  Do any equal 1?
               È  Ã      :Pass the integers in each remaining sub-array through a function
                aY       :  Get the absolute difference with the integer's index
              x          :Reduce by addition
             ñ           :Sort the main array by those values
                   ñ     :Return the first sub-array

Answer 5

Ruby, 120 score + 112 106 91 82 bytes

->n{(0...n).map{|a|a+(a+2)%5-([[],[],[0,4,3],[-1,4,4,4],[1,1,6,1]][n%5][a-n]||2)}}

Try it online!

The sequence is basically (a-2)+(a+2)%5.

If n mod 5 is not 0 or 1, the last 3 or 4 elements are different.

This is still half-hardcoded, always finds the best solution, maybe it could be golfed a little more, but I have run out of ideas.

Answer 6

JavaScript (Node.js), 148 score + 109 73 bytes

n=>[...Array(n)].map(_=>l=!m|l>n%5+2&&l>m+2?[+m,m=l+2][0]:l+2,m=n>4,l=~m)

Try it online! Explanation: l keeps track of the last number generated and m keeps track of the next number of the opposite parity to l; once l exceeds m+2 the variables are exchanged. An adjustment is made at the start of the sequence so that sequences whose lengths are not multiples of 5 do not miss out any numbers, and another adjustment is made for n=4.