Give a permutation with no two consecutive integers next to each other

Question

Challenge

Given an integer n ≥ 4, output a permutation of the integers [0, n-1] with the property that no two consecutive integers (integers with absolute difference 1) are next to each other.

Examples

• 4 → [1, 3, 0, 2]
• 5 → [0, 2, 4, 1, 3]
• 6 → [0, 2, 4, 1, 3, 5]
• 7 → [0, 2, 4, 1, 5, 3, 6]

You may use 1-indexing instead (using integers [1, n] instead of [0, n-1]).

Your code must run in polynomial time in n, so you can't try all permutations and test each one.

Answer 1

Jelly, 3 2 bytes

ḂÞ

Sorts the integers in [1, ..., n] by their LSB.

Try it online!

Answer 2

Python 2, 32 bytes

lambda n:(range(n|1)*2)[1:n*2:2]

Try it online!

Answer 3

Python 3, 40, 38 bytes

lambda n:[*range(1,n,2),*range(0,n,2)]

Try it online!

This runs in O(n) time.

Thanks to Dennis for saving 2 bytes!

Answer 4

Python 2, 34 bytes

lambda n:range(1,n,2)+range(0,n,2)

Try it online!

Python 2, 40 bytes

lambda n:[(k-~k)%(n|1)for k in range(n)]

Try it online!

Answer 5

Haskell, 22 bytes

f is a function of n that returns an appropriately ordered list. I am using the 1-indexing option.

f n=[2,4..n]++[1,3..n]

Answer 6

Octave, 17 bytes

@(x)[2:2:x,1:2:x]

Try it online!

This uses the same approach as many others. Concatenate two vectors, one with all the even number in the inclusive range 2 ... x, and all the odd numbers in the inclusive range 1 ... x. The syntax should be fairly obvious, so I won't explain that.

Answer 7

Gaia, 2 bytes

r∫

Try it online!

This simply (stable) ∫​orts the integers in the range [1, input] by their parity.

Answer 8

R, 39 36 35 bytes

function(x)c(seq(2,x,2),seq(1,x,2))

Try it online!

Answer 9

05AB1E, 3 bytes

Port of DJMcMayhem's Python answer and Dennis's Jelly answer

ÝΣÉ

Try it online!

How?

ÝΣÉ - implicitly take input onto stack  e.g. 7
Ý   - pop a and push range(a)               [0,1,2,3,4,5,6]
 Σ  - sort by (stable):
  É -   is even? (x%2==0 ?)                 [1,3,5,0,2,4,6]
    - implicit print of top of stack

Answer 10

JavaScript (ES6), 40 bytes

f=
n=>[...Array(i=n)].map(_=>(i+--i)%(n|1))

<input type=number min=4 oninput=o.textContent=f(+this.value).join`\n`><pre id=o>

Edit: Saved 1 byte thanks to @Arnauld.

Answer 11

Japt, 4 bytes

You could also replace u with v to get a different order.

õ ñu

Try it

Or, if we can ouput an array of 2 arrays:

õ ó

Try it

Answer 12

Mathematica, 50 -> 47 -> 42 bytes

p = Join[Range[2, #, 2], Range[1, #, 2]] &

Try it online!

Thanks to user202729 for pointing out the twofold optimization potential Join[] insteaed of Flatten[] and using pure functions.

I'd like to add two remarks.

1) It is fairly straightforward to construct a specific permutation with no falling or rising succession for n>=4 as requested n the OP.

It consists of two consecutive list.

For even n these are:
list1 = (2,4,...,n/2)
list2 = (1,3,...,n/2-1)

For odd n we have:
list1 = (2,4,...,Floor[n/2])
list2 = (1,3,...,Floor[n/2])

For this "algorithm" just one decision must be made (n even or odd), the rest is just writing down n numbers.

A possible Mathematica solution is provided at the top.

2) A related question is how many such permuations exist as a function of n.

Mathematica, 124 Bytes

a[0] = a[1] = 1; a[2] = a[3] = 0;
a[n_] := a[n] = (n + 1)*a[n - 1] - (n - 2)*a[n - 2] - (n - 5)*a[n - 3] + (n - 3)*a[n - 4]

Try it online!

Example:

a[#] & /@ Range[4, 12]

{2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034}

To count the number of such permutations is a standard problem.

For n = 4 there are 2: {{2,4,1,3},{3,1,4,2}}

For n = 5 there are 14: {{1,3,5,2,4},{1,4,2,5,3},{2,4,1,3,5},{2,4,1,5,3},{2,5,3,1,4},{3,1,4,2,5},{3,1,5,2,4},{3,5,1,4,2},{3,5,2,4,1},{4,1,3,5,2},{4,2,5,1,3},{4,2,5,3,1},{5,2,4,1,3},{5,3,1,4,2}}

The number a(n) of these permutations rises quickly: 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, ...

For large n the ratio a(n)/n! seems to approach the limit 1/e^2 = 0.135335... I have no strict proof but it is just a conjecture from numerical evidence. You can test this by trying to run the program online.

The program above (based on the reference given below) calculates these numbers.

You can find more information in the relevant sequence on OEIS: A002464. Hertzsprung's problem: ways to arrange n non-attacking kings on an n X n board, with 1 in each row and column. Also number of permutations of length n without rising or falling successions.

Answer 13

Ruby, 27 bytes

->n{[*2.step(n,2)]|[*1..n]}

Try it online!

Using 1-indexing

Answer 14

Whitespace, 161 bytes

Here is the official, uncommented submission: Try it online!

push_0   
read_n	
		push_0   
retreive_n			push_1  		
subtract	   dup_and_out[ 
 	
 	]label_s'
   
'push_2  		 
subtract	   dup[ 
 ]jump_next_if_neg:
		  
:dup_and_out[ 
 	
 	]else_jump_back:
 
 
:label_ss'
    
'push_0   
retreive_n			push_2  		 
subtract	   dup_and_out[ 
 	
 	]dup[ 
 ]jump_next:
 
    
:label_ssss'
      
'push_2  		 
subtract	   dup[ 
 ]jump_end_if_neg:
		   
:dup_and_out[ 
 	
 	]else_jump_back:
 
    
:label_sss'
     
'end

Try it online!

I sacrificed a few bytes so that the program would execute without any errors, I believe that I could lose around 7-8 bytes, and it would still output correctly, but it would also output error messages, and nobody wants that.

Full Byte Explanation:

[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][N][Tab][Tab][Tab][Tab]          Read input value and store in heap
[Space][Space][Space][N]                   Push a 0 on the stack again
[Tab][Tab][Tab]                            Retrieve the value from the heap
[Space][Space][Tab][Tab][N]                Push a -1 on the stack
[Tab][Space][Space][Space]                 Add -1 to value
[Space][N][Space]                          Duplicate 
[Tab][N][Space][Tab]                       Output
[N][Space][Space][Space][N]                Set First Label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][N]             If negative, jump to second label
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][N]                    Jump back to first label
[N][Space][Space][Space][Space][N]         Set Second Label
[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][Tab]                            Retrieve input value from heap again
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 This time, Add a -2 to the value
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[Space][N][Space]                          Duplicate
[N][Space][N][Space][Tab][N]               Jump to third label
[N][Space][Space][Space][Tab][N]           Set third label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][Space][N]      Jump to end if negative
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][Tab][N]               Jump back to third label
[N][Space][Space][Space][Space][Space][N]  Set fourth label/end
[N][N][N]                                  Terminate

Answer 15

Ruby, 27 bytes

->n{(1..n).sort_by{|i|i&1}}

As in this answer, n first integers are sorted by their least significant bit.

Try it online!

Answer 16

JavaScript (Node.js), 42 bytes

n=>(f=i=>i<n?[i,...f(i+2)]:i&1?[]:f(1))(0)

Try it online!

JavaScript (Node.js), 47 bytes

n=>(f=i=>i--?[n--*2%(N|1)+N%2,...f(i)]:[])(N=n)

Try it online!

Answer 17

F# (Mono), 27 bytes

let f n=[2..2..n]@[1..2..n]

Try it online!

Answer 18

Gol><>, 14 bytes

FL:2%Z}:3=?$|B

Try it online!

Example full program & How it works

1AGIE;GDlR~
FL:2%Z}:3=?$|B

1AG          Register row 1 as function G
   IE;       Take number input; halt on EOF
      GD     Call G and print the stack
        lR~  Empty the stack
             Repeat indefinitely

F           |   Repeat n times...
 L              Push loop counter (0..n-1)
  :2%Z}         If even, move to bottom of the stack
       :3=?$    If top == 3, swap top two
                  This is activated only once to make [2 0 3 1]
             B  Return

Answer 19

J, 10 bytes

i./:2|1+i.

Try it online!

Explanation:

  /:          sort
i.            the numbers in the range 0..n-1 
    2|        according the remainder mod 2 of 
      1+i.    the numbers in the range 1..n   

Answer 20

Java 8, 56 bytes

n->{for(int i=n;i>0;)System.out.println((i+--i)%(n|1));}

Port of @Neil's JavaScript (ES6) answer.

Try it online.

---

Old 66 bytes answer:

n->{String[]r={"",""};for(;n-->0;)r[n%2]+=n+" ";return r[0]+r[1];}

Try it online.

Explanation:

n->{                  // Method with integer parameter and String return-type
  String[]r={"",""};  //  Result-Strings, both starting empty
  for(;n-->0;)        //  Loop in the range (n, 0]
    r[i%2]+=i+" ";    //   Append `i` and a space to one of the two result-Strings,
                      //   depending on if it is even (first) or odd (second)
  return r[0]+r[1];}  //  Return the two result-Strings appended to each other