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

Question

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 2^n-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.

Answer 1

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

Answer 2

Haskell, 47 bytes

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

Answer 3

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.

Answer 4

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])

Answer 5

Mathematica, 57 54 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}}

Answer 6

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.

Answer 7

Pyth, 34 33 31 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))

Answer 8

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%%.*}

Answer 9

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]]

Answer 10

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);
    }
}

Answer 11

Jelly, 9 bytes

Œ!IṠIAƑƲƇ

Try it online!

How it works

Œ!IṠIAƑƲƇ - Main link. Takes an integer n on the left
Œ!        - Permutations of [1,2,...,n]
       ƲƇ - Keep those permutations for which the following is true:
  I       -   Forward increments
   Ṡ      -   Signs
    I     -   Forward increments
     AƑ   -   All non-negative?

To see why this works, take four permutations for \$n = 4\$:

• [2,1,3,4] which is a prepend-append permutation
• [3,2,1,4] which is a prepend-append permutation
• [3,1,4,2] which is not
• [1,2,4,3] which is not

Let's work through each of the 4 commands (I, Ṡ, I and AƑ) to see the difference. Each command is applied sequentially to the result of the previous one:

Command	[2,1,3,4]	[3,2,1,4]	[3,1,4,2]	[1,2,4,3]
I	[-1,2,1]	[-1,-1,3]	[-2,3,-2]	[1,2,-1]
Ṡ	[-1,1,1]	[-1,-1,1]	[-1,1,-1]	[1,1,-1]
I	[2,0]	[0,2]	[2,-2]	[0,-2]
AƑ	1	1	0	0

It turns out that always IṠI yields an array consisting of 2, 0 or -2, and that if a permutation does not contain -2 after IṠI is applied, the permutation is a prepend-append permutation.