Zdefiniuj sekwencję poprzedzającą-dołączającą długości, nktóra będzie permutacją liczb, 1, 2, ..., nktóre można wygenerować za pomocą następującej procedury:

• Zacznij od numeru 1.

• Dla każdej liczby od 2do n, umieść ten numer na początku lub na końcu sekwencji (albo prepend lub dołączenia go, stąd nazwa sekwencji).

Na przykład jest to prawidłowy sposób generowania sekwencji poprzedzającej-dołączającej o długości 4:

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

Twoim zadaniem jest zbudowanie programu lub funkcji, która pobierze liczbę nod 3do 30jako dane wejściowe, i wydrukuje lub zwróci wszystkie sekwencje długości przed dodaniem-dołączeniem w kolejności nleksykograficznej (jeśli wyprowadzasz ciągi, a nie listy, liczby powyżej 9 będą reprezentowane jako litery a-u, aby zachować długość łańcucha). Na przykład jest to kolejność dla n = 4:

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

Zasadniczo istnieją 2 ^n-1 permutacje-dopisywanie długości n.

W kodzie nie można używać żadnych wbudowanych funkcji sortujących w swoim języku. Najkrótszy program do wykonania tego w dowolnym języku wygrywa.

CJam, 22 20 19 17 bajtów

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

Rozszerzenie kodu :

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

Jak to działa :

To jest wersja debugowania kodu:

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

Zobaczmy, jak to działa dla danych wejściowych 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>|}/";

Wypróbuj online tutaj

Haskell, 47 bajtów

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

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

Wyświetla listę list liczb.

Rozwiązanie rekurencyjne. Do n==1wyjścia [[1]]. W przeciwnym razie dodaj nna początku lub na końcu wszystkich (n-1)uprawnień. Przechowywanie wstępne powoduje, że permutacja jest leksykograficznie późniejsza niż dodawanie, więc permutacje pozostają posortowane.

„Boolean” bkoduje, czy umieścić [n]na początku, czy na końcu. W rzeczywistości resztę listy przenosimy xw wyrażeniu x*b+[n]+x*-b. Wstawianie bjako -1lub 1pozwala używać odwracania przez negowanie, ponieważ lista pomnożona przez -1jest pustą listą.

Pyth, 19 lat

usCm,+dH+HdGr2hQ]]1

Wypróbuj online tutaj

Jest to pełny program, który pobiera dane wejściowe ze standardowego wejścia.

Działa to w podobny sposób jak rozwiązanie xnor, ale generuje wartości nieco nie w porządku, więc należy je zmienić. To, co dzieje się na każdym poziomie, polega na tym, że każda poprzednia lista wartości ma nową wartość dodaną na końcu i na początku, a każda z nich jest owinięta w 2-krotki, które są zawinięte razem w listę. Na przykład pierwszy krok to:

[[1]]
[([1,2], [2,1])]

Następnie ta lista krotek jest spakowana (a następnie sumowana w celu usunięcia listy najbardziej oddalonych). W pierwszym przypadku daje to po prostu rozpakowaną wartość z góry, ponieważ na liście jest tylko jedna wartość.

Kroki pokazujące 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, 57 54 49 bajtów

f@1={{1}};f@n_:=#@n/@f[n-1]&/@Append~Join~Prepend

Przykład:

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 bajtów

   0|:<:((,,.,~)1+#)@[&0,.@1:

   (0|:<:((,,.,~)1+#)@[&0,.@1:) 3
1 2 3
2 1 3
3 1 2
3 2 1

1-bajtowa poprawa dzięki FUZxxl .

Pyth 34 33 31 29

Zasadniczo tłumaczenie XNOR „s Python odpowiedź . Nadal nie jestem świetny w Pyth, więc sugestie ulepszeń są mile widziane.

Definiuje funkcję yzwracającą listę list liczb całkowitych.

L?]]1<b2smm++*kdb*k_dy-b1,1_1

Aktualizacja: Zapisano 2 bajty dzięki FryAmTheEggman .

Wyjaśnienie:

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

Pure Bash, 103

Dłużej niż się spodziewałem:

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

Implementacja JavaScript fajnego rozwiązania @ Optimizer.

Rekurencyjny (73):

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

Iteracyjny (74):

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

Przetestuj w konsoli Firefox / FireBug

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

Moje rozwiązanie Java:

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