# Generate the set of prepend-append permutations in lexicographically sorted order

Define a prepend-append sequence of length n to be a permutation of the numbers 1, 2, ..., n that can be generated by the following procedure:

• Start with the number 1.

• For each number from 2 to n, place this number to the beginning or end of the sequence (either prepend or append it, hence the name of the sequence).

For example, this is a valid way to generate a prepend-append sequence of length 4:

1
21     [beginning]
213    [end]
2134   [end]


Your task is to build a program or function that will take a number n from 3 to 30 as input, and print or return all prepend-append sequences of length n in lexicographical order (if you're outputting strings and not lists, numbers above 9 will be represented as letters a-u, to preserve string length). For example, this is that order for n = 4:

1234  [RRR]
2134  [LRR]
3124  [RLR]
3214  [LLR]
4123  [RRL]
4213  [LRL]
4312  [RLL]
4321  [LLL]


In general, there are 2n-1 prepend-append permutations of length n.

You may not use any built-in sorting functions in your language in your code. The shortest program to do this in any language wins.

• I'm not a fan of the output format requirement, in particular the conversion to letters a-u. Can we just output lists of numbers? – xnor Mar 6 '15 at 5:13
• You might want to accept the answer after some time as some people tend not to answer a question if it has an accepted answer. – Optimizer Mar 6 '15 at 9:27
• So you have wrong accepted answer .. – Optimizer Mar 6 '15 at 18:38
• FryAmTheEggman posted his answer 21 minutes before you edited yours. – Joe Z. Mar 6 '15 at 18:41
• @Optimizer I don't quite think it's the weirdest way - FryAmTheEggman's answer was 19 bytes long 21 minutes before yours was. That makes it the earliest-posted shortest answer. – Joe Z. Mar 6 '15 at 19:21

# CJam, 22 20 19 17 bytes

]]l~{)f+_1fm>|}/p


Code expansion:

]]                   "Put [[]] onto stack. What we will do with this array of array is";
"that in each iteration below, we will first append the next";
"number to all present arrays, then copy all the arrays and";
"move the last element to first in the copy";
l~                 "Read input number. Lets call it N";
{         }/     "Run this code block N times ranging from 0 to N - 1";
)f+             "Since the number on stack starts from 0, add 1 to it and append";
"it to all arrays in the array of array beginning with [[]]";
_1fm>        "Copy the array of array and move last element from all arrays";
"to their beginning";
|       "Take set union of the two arrays, thus joining them and eliminating";
"duplicates. Since we started with and empty array and started adding";
"numbers from 1 instead of 2, [1] would have appeared twice if we had";
"simply done a concat";
p    "Print the array of arrays";


How it works:

This is a debug version of the code:

]]l~ed{)edf+ed_ed1fm>ed|ed}/edp


Let's see how it works for input 3:

[[[]] 3]                                 "]]l~"            "Empty array of array and input";
[[[]] 1]                                 "{)"              "First iteration, increment 0";
[[[1]]]                                  "{)f+"            "Append it to all sub arrays";
[[[1]] [[1]]]                            "{)f+_"           "Copy the final array of array";
[[[1]] [[1]]]                            "{)f+_1fm>"       "shift last element of each";
"sub array to the beginning";
[[[1]]]                                  "{)f+_1fm>|}"     "Take set based union";
[[[1]] 2]                                "{)"              "2nd iteration. Repeat";
[[[1 2]]]                                "{)f+"
[[[1 2]] [[1 2]]]                        "{)f+_";
[[[1 2]] [[2 1]]]                        "{)f+_1fm>";
[[[1 2] [2 1]]]                          "{)f+_1fm>|}";
[[[1 2] [2 1]] 3]                        "{)";
[[[1 2 3] [2 1 3]]]                      "{)f+"
[[[1 2 3] [2 1 3]] [[1 2 3] [2 1 3]]]    "{)f+_";
[[[1 2 3] [2 1 3]] [[3 1 2] [3 2 1]]]    "{)f+_1fm>";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm>|}";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm>|}/";


Try it online here

f 1=[[1]]
f n=(\x->map(++[n])x++map(n:)x)$f$n-1

• Switching to list comprehension saves a few bytes: f n=[[n:x,x++[n]]|x<-f$n-1]>>=id (using the code-golfers concat function >>=id). – nimi Mar 6 '15 at 17:42 • @nimi but its in the wrong order r – proud haskeller Mar 7 '15 at 22:03 • @proudhaskeller: Oh dear, didn't read the spec carefully enough. I tried to fix it and found four slightly different ways all of the same length as @alephalpha's version, so I can't offer an improvement. f n=[x++[n]|x<-f$n-1]++[n:x|x<-f$n-1], f n=map(++[n])(f$n-1)++[n:x|x<-f$n-1], f n=map(++[n])(f$n-1)++map(n:)(f$n-1), f n=(++[n])#n++(n:)#n;p#i=map p$f$i-1 – nimi Mar 8 '15 at 23:42 # Python 2, 68 f=lambda n:[[1]]*(n<2)or[x*b+[n]+x*-b for b in[1,-1]for x in f(n-1)]  Outputs a list of lists of numbers. A recursive solution. For n==1, output [[1]]. Otherwise, add n to the start or end of all (n-1)-permutations. Prepending makes the permutation lexicographically later than appending, so the permutations remain sorted. The "Boolean" b encodes whether to put [n] at the start or end. Actually, we move the rest of the list x in the expression x*b+[n]+x*-b. Putting b as -1 or 1 lets use flip by negating, since a list multiplied by -1 is the empty list. # Pyth, 19 usCm,+dH+HdGr2hQ]]1  Try it online here This is a full program that takes input from stdin. This works in a similar way to xnor's solution, but generates the values a bit out of order, so they must be reordered. What happens at each level is that each previous list of values has the new value added to the end and to the beginning and these are each wrapped in a 2-tuple which are wrapped together in a list. For example, the first step does this: [[1]] [([1,2], [2,1])]  Then, this list of tuples is zipped (and then summed to remove the outermost list). In the first case this just gives the unwrapped value from above, as there is only one value in the list. Steps showing 2->3: ([1,2], [2,1]) [([1,2,3],[3,1,2]),([2,1,3],[3,2,1])] ([1,2,3],[2,1,3],[3,1,2],[3,2,1])  # Mathematica, 5754 49 bytes f@1={{1}};f@n_:=#@n/@f[n-1]&/@Append~Join~Prepend  Example: f[4]  {{1, 2, 3, 4}, {2, 1, 3, 4}, {3, 1, 2, 4}, {3, 2, 1, 4}, {4, 1, 2, 3}, {4, 2, 1, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}} # J, 26 bytes  0|:<:((,,.,~)1+#)@[&0,.@1: (0|:<:((,,.,~)1+#)@[&0,.@1:) 3 1 2 3 2 1 3 3 1 2 3 2 1  1-byte improvement thanks to FUZxxl. • Substitute ,. for ,"1 for one character. – FUZxxl Mar 6 '15 at 10:54 # Pyth, 343331 29 Basically a translation of xnor's Python answer. I'm still not great with Pyth, so improvement suggestions are welcome. Defines a function y to return a list of lists of integers. L?]]1<b2smm++*kdb*k_dy-b1,1_1  Update: Saved 2 bytes thanks to FryAmTheEggman. Explanation: L define a function y with argument b that returns ?*]]1<b2 [[1]] if b < 2 else s sum( m map(lambda d: m map(lambda k: ++*kdb*k_d k*d + [b] + k*-d y-b1 , y(b - 1)) ,1_1) , (1, -1))  • Some pyth stuff: -b1 can be tb, [1_1) can be ,1_1 (however you can just drop the close bracket as you only need to count the bytes needed to make the function, even though you won't be able to call it without closing it), and you don't need to wrap b in a list as pyth automatically converts to list when adding a list to an int. – FryAmTheEggman Mar 6 '15 at 15:18 • I came up with a way to save several bytes by manually doing the second map over [1,-1]. I can save bytes to hardcode something that short, especially when you simplify the logic. I get L?]]1<b2sCm,+db+bdytb – FryAmTheEggman Mar 6 '15 at 16:03 • @FryAmTheEggman You might actually want to add that as your own answer. That's just awesome. – PurkkaKoodari Mar 6 '15 at 16:05 • OK, I wanted to try to beat CJam before posting but I guess the zip trick is interesting enough to merit posting it. Good luck with Pyth ;) – FryAmTheEggman Mar 6 '15 at 16:27 # Pure Bash, 103 Longer than I'd hoped: a=1..1 for i in {2..9} {a..u};{ ((++c<$1))||break
a={${a// /,}} a=eval echo$a$i$i$a } echo${a%%.*}


# JavaScript (ES6) 73 80

JavaScript implementation of @Optimizer's nice solution.

Recursive (73):

R=(n,i=1,r=[[1]])=>++i>n?r:r.map(e=>r.push([i,...e])+e.push(i))&&R(n,i,r)


Iterative (74):

F=n=>(i=>{for(r=[[1]];++i<=n;)r.map(e=>r.push([i,...e])+e.push(i))})(1)||r


Test In Firefox/FireBug console

R(4)


[[1, 2, 3, 4], [2, 1, 3, 4], [3, 1, 2, 4], [3, 2, 1, 4], [4, 1, 2, 3], [4, 2, 1, 3], [4, 3, 1, 2], [4, 3, 2, 1]]

My Java solution:

public static void main(String[] args) {
listPrependAppend(4);
}

private static void listPrependAppend(int n) {
int total = (int) Math.pow(2, n - 1);
int ps;
boolean append;
String sequence;
String pattern;

for (int num = 0; num < total; num++) {
sequence = "";
pattern = "";
append = false;
ps = num;
for (int pos = 1; pos < n + 1; pos++) {
sequence = append ? (pos + sequence) : (sequence + pos);
append = (ps & 0x01) == 0x01;
ps = ps >> 1;
if (pos < n) {
pattern += append ? "L" : "R";
}
}
System.out.format("%s\t[%s]%n", sequence, pattern);
}
}

• Oh fark, now after seeing the other answers I see what you mean about shortest answer. – Brett Ryan Mar 8 '15 at 6:19
• While your solution is respectable, concise, and well-presented in its own right, you're correct that it's not quite a candidate for the problem at hand. – Joe Z. Mar 8 '15 at 7:42
• @BrettRyan You can make your code much shorter by removing unnecessary whitespace and using one-char variable names. You can also replace false by something like 5<4. – ProgramFOX Mar 8 '15 at 7:44
• Thanks guys. It was my first attempt at participating in code challenges. I was just looking for some programming challenges and didnt realise the target was to get the shortest solution. :) Thanks for letting me participate. – Brett Ryan Mar 8 '15 at 8:39