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
For each number from
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
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
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.