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.
When you say "output a permutation", do you mean as a list? Or can we produce a function that implements the permutation mapping itself? – xnor – 2018-05-13T16:54:48.007
@xnor It should be outputted in some human readable form. I don't care exactly how. – Anush – 2018-05-13T16:55:17.300
Would
[[1,3],[0,2]]
be an acceptable output format? – Shaggy – 2018-05-13T20:23:23.293@Shaggy It's not great. Does it mean 1,3,0,2? – Anush – 2018-05-13T20:28:13.140
Related – Peter Taylor – 2018-05-14T05:53:19.017
The related question demands no output if not possible. This one avoids that by eliminating the only inputs where it isn’t possible (I<4). – WGroleau – 2018-05-14T08:28:32.913