Generera uppsättningen prependut-append-permutationer i lexikonografiskt sorterad ordning

Joe Z. 03/06/2015. 10 answers, 658 views
code-golf combinatorics

Definiera en prepend-append sequence med längden n att vara en permutation av numren 1, 2, ..., n som kan genereras med följande procedur:

  • Börja med nummer 1 .

  • För varje nummer från 2 till n , placera detta nummer till början eller slutet av sekvensen (antingen prepend eller append det, följaktligen sekvensens namn).

Det här är till exempel ett giltigt sätt att generera en prepend-append-sekvens med längd 4:

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

Din uppgift är att bygga ett program eller en funktion som tar ett tal n från 3 till 30 som inmatning och skriv ut eller returnera alla prepend-append-sekvenser av längd n i lexikonografisk ordning (om du skriver ut strängar och inte listor, siffror ovan 9 kommer att representeras som bokstäver a-u , för att bevara stränglängden). Detta är till exempel den ordningen för n = 4 :

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

I allmänhet finns det 2 n-1 prepend-append-permutationer med längd n .

Du får inte använda några inbyggda sorteringsfunktioner på ditt språk i din kod. Det kortaste programmet att göra detta på vilket språk som helst vinner.

5 Comments
xnor 03/06/2015
Jag är inte ett fan av kravet på utdataformat, i synnerhet omvandlingen till bokstäver a-u . Kan vi bara skriva ut listor med siffror?
3 Optimizer 03/06/2015
Du kanske vill acceptera svaret efter en tid eftersom vissa människor brukar inte svara på en fråga om det har ett godkänt svar.
1 Optimizer 03/06/2015
Så du har fel accepterat svar ..
2 Joe Z. 03/06/2015
FryAmTheEggman skrev sitt svar 21 minuter innan du redigerade din.
2 Joe Z. 03/06/2015
@Optimizer Jag tycker inte riktigt att det är det konstigaste sättet - FryAmTheEggman svar var 19 byte långt 21 minuter innan ditt var. Det gör det till det kortaste svaret.

10 Answers


Optimizer 03/06/2015.

CJam, 22 20 19 17 byte

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

Detta är en debug-version av koden:

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

Låt oss se hur det fungerar för inmatning 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>|}/"; 

Prova det online här


alephalpha 03/06/2015.

Haskell, 47 byte

f 1=[[1]]
f n=(\x->map(++[n])x++map(n:)x)$f$n-1 
3 comments
1 nimi 03/06/2015
Byte till listaförståelse sparar några byte: f n=[[n:x,x++[n]]|x<-f$n-1]>>=id (med kod-golfers concat funktion >>=id ).
1 proud haskeller 03/07/2015
@nimi men i fel ordning r
nimi 03/08/2015
@proudhaskeller: Åh kära, läste inte specen noggrant nog. Jag försökte fixa det och hittade fyra lite olika sätt på samma sätt som @ alephalphas version, så jag kan inte erbjuda en förbättring. 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

xnor 03/06/2015.

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

Utför en lista med listor med siffror.

En rekursiv lösning. För n==1 , utgång [[1]] . Annars lägger du till n till början eller slutet av alla (n-1) -permutationer. Förutbestämning gör permutationen lexikografiskt senare än att lägga till, så permutationerna förblir sorterade.

Den "Boolean" b kodar om du vill sätta [n] i början eller slutet. I själva verket flyttar vi resten av listan x i uttrycket x*b+[n]+x*-b . Att lägga b som -1 eller 1 låter använda flip genom att negera, eftersom en lista multiplicerad med -1 är den tomma listan.


FryAmTheEggman 03/06/2015.

Pyth, 19

usCm,+dH+HdGr2hQ]]1 

Prova det online här

Detta är ett komplett program som tar in data från stdin.

Detta fungerar på samma sätt som xnors lösning, men genererar värdena lite i ordning, så de måste ombeställas. Vad som händer på varje nivå är att varje tidigare värdeslista har det nya värdet lagt till i slutet och till början och dessa är var och en inslagna i en 2-tupel som är insvept i en lista. Till exempel gör det första steget detta:

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

Därefter zippas denna lista med tuples (och summeras sedan för att ta bort den yttersta listan). I det första fallet ger detta bara det oöppnade värdet från ovan, eftersom det bara finns ett värde i listan.

Steg som visar 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]) 

alephalpha 03/06/2015.

Mathematica, 57 54 49 bytes

f@1=NO 

Exempel:

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


randomra 04/13/2017.

J, 26 byte

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

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

1-byte förbättring tack vare FUZxxl .

1 comments
FUZxxl 03/06/2015
Suppleant,. för ,"1 för ett tecken.

Pietu1998 04/13/2017.

Pyth, 343331 29

I grund och botten en översättning av xnors Python svar . Jag är fortfarande inte bra med Pyth, så förbättringsförslag är välkomna.

Definierar en funktion y att returnera en lista över heltal.

L?]]1 

Update: Sparade 2 byte tack vare FryAmTheEggman .

Förklaring:

L                                  define a function y with argument b that returns
 ?*]]1 
4 comments
FryAmTheEggman 03/06/2015
Några smutsiga saker: -b1 kan vara tb , [1_1) kan vara ,1_1 (men du kan bara släppa nära hållaren eftersom du bara behöver räkna de byte som behövs för att göra funktionen, även om du inte kommer att kunna ringa det utan att stänga det), och du behöver inte böja b i en lista som python konverteras automatiskt till lista när du lägger till en lista på en int.
FryAmTheEggman 03/06/2015
Jag kom fram med ett sätt att spara flera byte genom att manuellt göra den andra kartan över [1,-1] . Jag kan spara byte för att hardkoda något som är kort, särskilt när du förenklar logiken. Jag får L?]]1
Pietu1998 03/06/2015
@FryAmTheEggman Du kanske vill lägga till det som ditt eget svar. Det är bara fantastiskt.
FryAmTheEggman 03/06/2015
OK, jag ville försöka slå CJam innan du skickade in, men jag antar att zip-tricket är intressant nog att förtjänar att lägga ut det. Lycka till med Pyth;)

edc65 03/07/2015.

JavaScript (ES6) 73 80

JavaScript-implementering av @ Optimizer bra lösning.

Rekursiv (73):

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

Iterativ (74):

 F=n=>(i=>NO 

Test Firefox / FireBug-konsolen

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


Digital Trauma 03/06/2015.

Pure Bash, 103

Längre än jag hade hoppats:

a=1..1
for i in {2..9} {a..u};{
((++c<$1))||break
a={${a// /,}}
a=`eval echo $a$i $i$a`
}
echo ${a%%.*} 

Brett Ryan 03/08/2015.

Min Java-lösning:

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);
    }
} 
4 comments
Brett Ryan 03/08/2015
Åh fark, nu efter att ha sett de andra svaren ser jag vad du menar om kortaste svaret.
2 Joe Z. 03/08/2015
Medan din lösning är respektabel, koncis och välpresenterad i sin egen rätt, är du korrekt att det inte är en riktig kandidat till det aktuella problemet.
1 ProgramFOX 03/08/2015
@BrettRyan Du kan göra din kod mycket kortare genom att ta bort onödigt blankutrymme och använda variabla namn med ett tecken. Du kan också ersätta false med något som 5<4 .
1 Brett Ryan 03/08/2015
Tack hörni. Det var mitt första försök att delta i kodutmaningar. Jag letade bara efter några programutmaningar och insåg inte att målet var att få den kortaste lösningen. :) Tack för att du lät mig delta.

Related questions

Hot questions

Language

Popular Tags