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.
CJam, 22 20 19 17 bytes

]]l~{)f+_1fm&gt;|}/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&gt;        "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&gt;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&gt;"       "shift last element of each";
                                                           "sub array to the beginning";
[[[1]]]                                  "{)f+_1fm&gt;|}"     "Take set based union";
[[[1]] 2]                                "{)"              "2nd iteration. Repeat";
[[[1 2]]]                                "{)f+"
[[[1 2]] [[1 2]]]                        "{)f+_";
[[[1 2]] [[2 1]]]                        "{)f+_1fm&gt;";
[[[1 2] [2 1]]]                          "{)f+_1fm&gt;|}";
[[[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&gt;";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm&gt;|}";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm&gt;|}/";


Try it online here