15
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
10
  • \$\begingroup\$ 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? \$\endgroup\$ Commented Mar 6, 2015 at 5:13
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ Commented Mar 6, 2015 at 9:27
  • 1
    \$\begingroup\$ So you have wrong accepted answer .. \$\endgroup\$ Commented Mar 6, 2015 at 18:38
  • 2
    \$\begingroup\$ FryAmTheEggman posted his answer 21 minutes before you edited yours. \$\endgroup\$ Commented Mar 6, 2015 at 18:41
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ Commented Mar 6, 2015 at 19:21

11 Answers 11

Reset to default
10
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
0
6
\$\begingroup\$

Haskell, 47 bytes

f 1=[[1]] f n=(\x->map(++[n])x++map(n:)x)$f$n-1
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ Commented Mar 6, 2015 at 17:42
  • 1
    \$\begingroup\$ @nimi but its in the wrong order r \$\endgroup\$ Commented Mar 7, 2015 at 22:03
  • \$\begingroup\$ @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 \$\endgroup\$ Commented Mar 8, 2015 at 23:42
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

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])
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Substitute ,. for ,"1 for one character. \$\endgroup\$ Commented Mar 6, 2015 at 10:54
1
\$\begingroup\$

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))
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Mar 6, 2015 at 15:18
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Mar 6, 2015 at 16:03
  • \$\begingroup\$ @FryAmTheEggman You might actually want to add that as your own answer. That's just awesome. \$\endgroup\$ Commented Mar 6, 2015 at 16:05
  • \$\begingroup\$ 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 ;) \$\endgroup\$ Commented Mar 6, 2015 at 16:27
1
\$\begingroup\$

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%%.*}
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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); } }
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Oh fark, now after seeing the other answers I see what you mean about shortest answer. \$\endgroup\$ Commented Mar 8, 2015 at 6:19
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Commented Mar 8, 2015 at 7:42
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Commented Mar 8, 2015 at 7:44
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Mar 8, 2015 at 8:39
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.