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
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.
Þ stable sort, because it's implemented using Python sorted function, which is guaranteed to be stable.
\$\endgroup\$
May 14, 2018 at 10:05
lambda n:[*range(1,n,2),*range(0,n,2)]
This runs in O(n) time.
Thanks to Dennis for saving 2 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]
@(x)[2:2:x,1:2:x]
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.
3 and 2 next to each other in f(4)?
\$\endgroup\$
Port of DJMcMayhem's Python answer and Dennis's Jelly answer
ÝΣÉ
ÝΣÉ - 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
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.
You could also replace u with v to get a different order.
õ ñu
Or, if we can ouput an array of 2 arrays:
õ ó
4, unfortunately; you can fix the first one by changing u to v or o to õ.
\$\endgroup\$
May 14, 2018 at 4:02
p = Join[Range[2, #, 2], Range[1, #, 2]] &
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.
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]
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.
[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\$
May 15, 2018 at 16:45
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
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.
[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
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\$
May 15, 2018 at 11:46
n=>(f=i=>i<n?[i,...f(i+2)]:i&1?[]:f(1))(0)
n=>(f=i=>i--?[n--*2%(N|1)+N%2,...f(i)]:[])(N=n)
FL:2%Z}:3=?$|B
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
i./:2|1+i.
/: 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
n->{for(int i=n;i>0;)System.out.println((i+--i)%(n|1));}
Port of @Neil's JavaScript (ES6) answer.
Old 66 bytes answer:
n->{String[]r={"",""};for(;n-->0;)r[n%2]+=n+" ";return r[0]+r[1];}
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
->n{(1..n).sort_by{|i|i&1}}
As in this answer, n first integers are sorted by their least significant bit.
[[1,3],[0,2]]be an acceptable output format? \$\endgroup\$