18
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ When you say "output a permutation", do you mean as a list? Or can we produce a function that implements the permutation mapping itself? \$\endgroup\$ – xnor May 13 '18 at 16:54
  • \$\begingroup\$ @xnor It should be outputted in some human readable form. I don't care exactly how. \$\endgroup\$ – Anush May 13 '18 at 16:55
  • \$\begingroup\$ Would [[1,3],[0,2]] be an acceptable output format? \$\endgroup\$ – Shaggy May 13 '18 at 20:23
  • \$\begingroup\$ @Shaggy It's not great. Does it mean 1,3,0,2? \$\endgroup\$ – Anush May 13 '18 at 20:28
  • \$\begingroup\$ Related \$\endgroup\$ – Peter Taylor May 14 '18 at 5:53

20 Answers 20

31
\$\begingroup\$

Jelly, 3 2 bytes

ḂÞ

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Wow! That is amazing. \$\endgroup\$ – Anush May 13 '18 at 17:01
  • 2
    \$\begingroup\$ “Sort by LSB” means that every other one moves to the beginning, but does the definition of Jelly require that the numbers in each half remain in their original order? If not, 100 (4) could be next to 101 (5) and still be “sorted by LSB”. Not faulting your code, but perhaps the describing comment isn’t complete? \$\endgroup\$ – WGroleau May 14 '18 at 8:18
  • 1
    \$\begingroup\$ @WGroleau Yes, Þ stable sort, because it's implemented using Python sorted function, which is guaranteed to be stable. \$\endgroup\$ – user202729 May 14 '18 at 10:05
  • 3
    \$\begingroup\$ The algorithm is more impressive to me than the small size, in its cleverness. You could also, I suppose, reverse the bit order, sort, and reverse it back. \$\endgroup\$ – WGroleau May 14 '18 at 10:53
  • 4
    \$\begingroup\$ There can only be 65536 different two byte Jelly programs. It is amazing so many of those turn out to be answers to ppcg challenges. \$\endgroup\$ – Anush May 15 '18 at 18:58
16
\$\begingroup\$

Python 2, 32 bytes

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

Try it online!

\$\endgroup\$
8
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Winner of the fastest prize! :) \$\endgroup\$ – Anush May 13 '18 at 16:59
  • \$\begingroup\$ Fastest running, or first posted? \$\endgroup\$ – WGroleau May 14 '18 at 8:23
  • 2
    \$\begingroup\$ @WGroleau First posted. \$\endgroup\$ – user202729 May 14 '18 at 10:07
6
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Aren't 3 and 2 next to each other in f(4)? \$\endgroup\$ – pajonk May 14 '18 at 7:53
  • \$\begingroup\$ Oops... fixed. Same byte count. :-) \$\endgroup\$ – Stewie Griffin May 14 '18 at 9:56
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

Gaia, 2 bytes

r∫

Try it online!

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

\$\endgroup\$
  • \$\begingroup\$ Same comment as on Jelly: does the algorithm or the definition of the language guarantee that the two halves each remain in their original order? \$\endgroup\$ – WGroleau May 14 '18 at 8:21
  • \$\begingroup\$ @WGroleau Yes, in Gaia, the sort meta-operator is stable. \$\endgroup\$ – Mr. Xcoder May 14 '18 at 11:34
5
\$\begingroup\$

R, 39 36 35 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ There is a trailing NA for odd numbers. \$\endgroup\$ – JayCe May 13 '18 at 19:26
  • \$\begingroup\$ tio.run/#%23K/qfZvs/… \$\endgroup\$ – JayCe May 13 '18 at 20:35
  • \$\begingroup\$ Wife's fault. We had to go on our bike ride before I could fix that. But you shaved some bytes off too. \$\endgroup\$ – ngm May 13 '18 at 23:16
  • \$\begingroup\$ Yeah I felt bad asking you to add bytes so I had to find a way to remove some... it worked out well. \$\endgroup\$ – JayCe May 13 '18 at 23:49
  • 1
    \$\begingroup\$ inspired by the octave answer \$\endgroup\$ – Giuseppe May 14 '18 at 12:02
4
\$\begingroup\$

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

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

\$\endgroup\$
  • \$\begingroup\$ Technically the second one outputs a list of numbers separated by commas ;-) Both fail on 4, unfortunately; you can fix the first one by changing u to v or o to õ. \$\endgroup\$ – ETHproductions May 14 '18 at 4:02
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @ Stewie Griffin As I am new here, please explain in more detail what you mean. In my first remark I have provided an algorithm and a code which solves the problem in polynomial time. Hence it should be considered a solution to the challenge. The second part extends the interesting problem. Hence it should be regarded as a comment. \$\endgroup\$ – Dr. Wolfgang Hintze May 15 '18 at 11:14
  • \$\begingroup\$ I took the liberty of slightly modifying your submission so your Mathematica code is at the top. With code-golf challenges it's mandatory to provide actual code (shortest possible). The way I formatted it it becomes a Mathematica answer as you probably intended it to be, and still has your original explanation below it. If you feel something is missing or I incorrectly edited your initial answer, feel free to edit it yourself again. Welcome to PPCG! :) \$\endgroup\$ – Kevin Cruijssen May 15 '18 at 12:04
  • \$\begingroup\$ @ Kevin Cruijssen Thank you very much for th warm welcome and the editing of my naive submission. I have now added a Mathematica program for the second remark. Which is most probably not lege artis. Most of all I don't know how to create the nice "try it online" link. \$\endgroup\$ – Dr. Wolfgang Hintze May 15 '18 at 15:08
  • \$\begingroup\$ Any link can be created using [some text](the_link). As for the "Try it online" link in particular, the website https://tio.run/ that's being hosted by our very own @Dennis contains links to all kind of programming languages. Wolfram Language (Mathematica) is one of them. At the top you can then click the play button to run the code, or the hyperlink button to copy "Try it online." (markup-)links. And you can split your code into actual "Code" (your submission), with an optional header/footer for (pretty-)printing one or multiple testcases. \$\endgroup\$ – Kevin Cruijssen May 15 '18 at 16:45
  • \$\begingroup\$ Apologies for my somewhat blunt comment, and lack of reply thereafter! The answer appeared in the review queue, and I didn't notice the code because of the formatting. It's not uncommon that new users posts "interesting observations" to challenges, without providing an actual answer to it. While it's done in good faith, it's not what the site is about. I thought this was such an answer. I should have responded to your comment, but I was in a hurry and couldn't write a new comment, so instead I just removed the old one. Apologies! And welcome to the site! I hope you'll stick around! :) \$\endgroup\$ – Stewie Griffin May 16 '18 at 13:38
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 27 bytes

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

Try it online!

Using 1-indexing

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Some things to golf: push_0, read_STDIN_as_int, push_0, retrieve can be push_0, duplicate_0, read_STDIN_as_int, retrieve to save a byte. And the first label can be an empty one with NSSN instead of NSSSN (and then the second label can be NSSSN; third NSSTN; and fourth NSSSSN). This should save 8 bytes as well. Also, you can remove the first Jump_to_third_label because you have the Set_third_label right below it already. In total: 140 bytes; (or with comments: Try it online.) -3 bytes if you remove NNN exit. \$\endgroup\$ – Kevin Cruijssen May 15 '18 at 11:46
1
\$\begingroup\$

F# (Mono), 27 bytes

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

Try it online!

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

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

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

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

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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