P Pr Pre Pref Prefi Prefix Präfixe Präfixe

34

Wenn Sie eine endliche Liste haben, geben Sie eine Liste aller Präfixe zurück, einschließlich einer leeren Liste, und zwar in aufsteigender Reihenfolge ihrer Länge.

(Grundsätzlich die Haskell-Funktion implementieren inits.)

Einzelheiten

  • Die Eingabeliste enthält Zahlen (oder einen anderen Typ, falls zweckmäßiger).
  • Die Ausgabe muss eine Liste von Listen sein .
  • Die Einreichung kann, muss aber keine Funktion sein, es kann jede Standard-E / A verwendet werden.
  • Für alle trivialen Lösungen gibt es eine CW-Antwort .

Beispiel

[] -> [[]]
[42] -> [[],[42]]
[1,2,3,4] -> [[], [1], [1,2], [1,2,3], [1,2,3,4]]
[4,3,2,1] -> [[], [4], [4,3], [4,3,2], [4,3,2,1]]
fehlerhaft
quelle
Wenn eine Sprache keine anderen Typen als Zeichen definiert, kann ich bei einem vollständigen Programm die Eingabe als Zeichenfolge und durch Zeilenumbrüche trennen?
NieDzejkob
@NieDzejkob Ich bin mir nicht sicher, welchen Konsens es für diesen Fall gibt, aber die Antwort von Brainfuck scheint so etwas zu tun.
Fehler
Können wir damit rechnen, dass die Liste mit null abgeschlossen wird?
Es ist besonders häufig in C / C ++, wobei die Hauptverwendung Strings sind.
@Rogem Wenn es so verbreitet ist, halte ich es für vernünftig, es zuzulassen.
Fehler

Antworten:

15

Haskell , 20 Bytes

Edit: Noch ein Byte kürzer mit einem ganz anderen Scan.

Eine anonyme Funktion, die den Trivialimport leicht übertrifft.

scanr(\_->init)=<<id

Probieren Sie es online!

  • Verwendet =<<für die Abkürzung (scanr(\_->init)=<<id) l = scanr(\_->init) l l.
  • Durchsucht eine Liste lvon rechts nach links und sammelt mit der Funktion Zwischenergebnisse \_->init.
  • Diese Funktion ignoriert die durchsuchten Elemente (sie werden nur verwendet, um die richtige Gesamtlänge für die gesammelten Ergebnisse zu erhalten), sodass das Anwenden initauf den Anfangswert des Scans, der auch ist , wirklich iteriert wird l.
Ørjan Johansen
quelle
13

Brainfuck , 21 12 Bytes

-9 Bytes dank Arnauld, der das Trennzeichen ÿanstelle von Zeilenumbrüchen vorschlägt

-[[<]>[.>],]

Probieren Sie es online!

Nimmt Bytes durch STDIN ohne Null-Bytes und druckt eine Reihe von Präfixen, die durch das ÿZeichen mit einem führenden ÿZeichen getrennt sind. Für die Eingabe Prefixesist beispielsweise die Ausgabe ÿÿPÿPrÿPreÿPrefÿPrefiÿPrefixÿPrefixeÿPrefixes.

Zur besseren Lesbarkeit finden Sie hier eine Version mit Zeilenumbrüchen .

Erläuterung:

-              Create a ÿ character in cell 0
 [        ,]   While input, starting with the ÿ
  [<]>           Go to the start of the string
      [.>]       Print the string
          ,      Append the input to the end of the string
Scherzen
quelle
1
Dies funktioniert nur bei BF-Implementierungen mit 8-Bit-Wrapping-Zellen ohne Vorzeichen.
Dev
11

JavaScript (ES6), 33 Byte

a=>[b=[],...a.map(n=>b=[...b,n])]

Probieren Sie es online!

Wie?

+--- a = input array
|
|       +--- initialize b to an empty array and include it as the first entry
|       |    of the output (whatever the input is)
|       |
|       |          +--- for each value n in a[]:
|       |          |
|       |          |        +--- append n to b[] and include this new array in
|       |          |        |    the final output
|       |          |        |
a => [b = [], ...a.map(n => b = [...b, n])]
               |                  |
               +---------+--------+
                         |
      spread syntax: expands all elements of
      the child array within the parent array
Arnauld
quelle
Wow, das ist eine
Brian H.
@BrianH. Vielen Dank! Einfache Aufgaben sind gute Gelegenheiten, detaillierte Erklärungen zu schreiben, die in dichterem Code nicht dargestellt werden können.
Arnauld
Hast du es von Hand gemacht? Oder haben Sie Hilfe von einer seltsamen Software bekommen, von der ich noch nie gehört habe?
Brian H.
2
Nur Notepad ++ mit etwas Spaltenmodusbearbeitung .
Arnauld
8

CW für alle trivialen Einträge

Sauber , 19 Bytes

Die Haskell-Version funktioniert auch in Clean.

import StdLib
inits

Probieren Sie es online!

Haskell , 22 Bytes

import Data.List
inits

Probieren Sie es online!

Prolog (SWI) , 6 Bytes

prefix

Probieren Sie es online!

ASCII
quelle
So zerrissen - um zu stimmen oder nicht. Einerseits schätze ich alle eingebauten Lösungen an einem Ort. Andererseits mag ich Builtins wirklich nicht, weil sie so einfach sind ...
6

Gelee , 3 Bytes

ṭṖƤ

Probieren Sie es online!

Wie es funktioniert

ṭṖƤ  Main link. Argument: A

  Ƥ  Map the link to the left over all non-empty(!) prefixes of A.
 Ṗ       Pop; remove the last element.
ṭ    Tack; append A to the resulting list.
Dennis
quelle
6

Japt , 4 Bytes

²£¯Y

Probieren Sie es online!

Erläuterung:

²       :Add an arbitrary extra item to the end of the array
 £      :For each item in the new array:
  ¯Y    : Get an array of the items that are before it
Kamil Drakari
quelle
6

Perl 6 , 13 Bytes

{(),|[\,] @_}

Probieren Sie es online!

Erklären:

In Perl 6 können Sie einen Operator alternativ in eckige Klammern setzen, um eine Listenreduktion zu schreiben. [+] @arrayGibt die Summe der Elemente in zurück @array, [*] @arraygibt das Produkt zurück usw. Sie können dem Operator auch einen Backslash voranstellen, um eine "dreieckige" Verkleinerung vorzunehmen, die in einigen Sprachen als "Scan" bezeichnet wird. So [\+] @arraygibt eine Liste des ersten Elements aus @array, dann die Summe der ersten beiden Elemente, dann die Summe der ersten drei Elemente usw.

Hier [\,] @_ist eine dreieckige Verkleinerung über das Eingangsarray@_ mit dem Listenerstellungsoperator ,. Es wird also eine Liste von Listen ausgewertet: das erste Element von @_, die ersten beiden Elemente von @_usw. Das ist fast das, was benötigt wird, aber das Problem erfordert zuerst eine einzelne leere Liste. Das erste Element der Rückgabeliste ist also eine wörtliche leere Liste (),, dann wird die Reduzierung über die Eingabeliste auf den Rest der Rückgabeliste mit abgeflacht |.

Sean
quelle
2
O_o was ist überhaupt hier los
ASCII
1
@ Nur ASCII- Dreiecksverkleinerung
user202729
5

R , 40 bis 39 Bytes

function(L)lapply(0:length(L),head,x=L)

Probieren Sie es online!

-1 Byte danke an digEmAll

Die Ausgabe von R's list Typ ist etwas seltsam; Es verwendet die sequentielle Indizierung, also zum Beispiel die Ausgabe für

list(1,2) ist

[[1]]                     # first list element
list()

[[2]]                     # second list element
[[2]][[1]]                # first element of second list element
[1] 1


[[3]]                     # third list element
[[3]][[1]]                # first element of third list element
[1] 1

[[3]][[2]]                # etc.
[1] 2

Die Eingabe als Vektor ergibt stattdessen ein übersichtlicheres Ausgabeformat, obwohl die Eingaben dann technisch nicht korrekt sind list.

Giuseppe
quelle
1
39 using lapply
digEmAll
@digEmAll danke!
Giuseppe
4

JavaScript, 36 Bytes

a=>[...a,0].map((x,y)=>a.slice(0,y))

Probieren Sie es online!

Oliver
quelle
4

Mathematica, 22 21 Bytes

-1 Byte danke an Mischa Lawrow !

{}~FoldList@Append~#&

Funktion pur. Nimmt eine Liste als Eingabe und gibt eine Liste von Listen als Ausgabe zurück. Ich halte das für die kürzest mögliche Lösung.

LegionMammal978
quelle
Wir können dieselbe Lösung kompakter schreiben als {}~FoldList@Append~#&.
Mischa Lawrow
@ Mischa Lawrow Danke! Ich hätte nicht gedacht, das gewählte 1 + 2-Argument so zu verwenden.
LegionMammal978
3

PowerShell , 65 Byte

param($a)'';$x=,0*($y=$a.count);0..--$y|%{$x[$_]=@($a[0..$_])};$x

Probieren Sie es online!

PowerShell rollt Listen-von-Listen hilfreich ab, wenn der Standardwert Write-Outputbei Programmabschluss auftritt, sodass Sie ein Element pro Zeile erhalten. Tack on a-join',' , um die Liste der Listen besser anzuzeigen, indem Sie die inneren Listen in Zeichenfolgen konvertieren.

(Ab) verwendet die Tatsache, dass der Versuch, ein leeres Array auszugeben (z. B. @()), zu keiner Ausgabe führt, sodass eine leere Array-Eingabe nur ''als Ausgabe dient, da $a[0..$_]dies zu nichts führt. Es werden auch einige spektakuläre Fehlermeldungen ausgegeben.

AdmBorkBork
quelle
Wenn Sie es in Parens einschließen, anstatt es zuzuweisen, sparen Sie 20 Byte . Es sei denn, Sie glauben nicht, dass dies als Rückgabe einer Liste von Listen gilt. Ich war immer bei dieser Unterscheidung verwirrt.
Veskah
@veskah Ja, das war fast das, was ich vor der Bearbeitung dieser Version hatte. Das Problem mit Ihrer oder meiner früheren Lösung - es wird keine Liste von Listen zurückgegeben. TIO1 vs TIO2
AdmBorkBork
3

K (ngn / k) , 8 Bytes

,\(,!0),

Probieren Sie es online!

ngn
quelle
1
Das ist eine Art Voodoo. ,\(,()),in K4. Beitritt zu eingetragenen Nullen bei eingetragenen Eingaben? wie geht das?
Streetster
1
@streetster ()ist eine leere Liste. (,()),xstellt es voran x. macht endlich ,\ einen concat-scan. dasx wird weggelassen, um eine Komposition zu bilden. Beachten Sie, dass das Trailing ,dyadisch ist, also "concat", nicht "enlist".
ngn
1
@streetster in k4 kann es ein Byte kürzer sein: 1_',\0,aber mein Parser ist nicht schlau genug, um damit umzugehen ...
umzugehen
3

Common Lisp , 39 Bytes

(defun f(l)`(,@(if l(f(butlast l))),l))

Probieren Sie es online!

Erläuterung

(defun f(l)                           )  ; Define a function f
           `(                        )   ; With the list (essentially capable of interpolation), containing:
             ,@                          ;     The value of, flattened to one level
               (if l              )      ;         If l is not the empty list (which is the representation of nil, i.e. the only falsy value)
                    (f(butlast l))       ;         Recurse with all of l but the tail
                                   ,l    ;     The value of l
Nur ASCII
quelle
3

F #, 53 Bytes

Ich habe tatsächlich zwei ziemlich ähnliche Antworten, beide gleich lang. Beide verwenden eine generische Sequenz sals Parameter.

Erste Lösung:

let i s=Seq.init(Seq.length s+1)(fun n->Seq.take n s)

Probieren Sie es online!

Seq.takeNimmt die ersten nElemente der Sequenz. Seq.initErstellt eine neue Sequenz mit einer Zählung (in diesem Fall) der Länge der Sequenz splus 1 und nimmt für jedes Element in der Sequenz die erste aufn Elemente auf s.

Zweite Lösung:

let i s=Seq.map(fun n->Seq.take n s){0..Seq.length s}

Ähnlich wie zuvor, mit der Ausnahme, dass eine Sequenz von 0 bis zur Länge von erstellt wird s . Nimmt dann diese Anzahl von Elementen ab s.

Versuchen Sie dies auch online!

Ciaran_McCarthy
quelle
fun s->Seq.map(fun n->Seq.take n s){0..Seq.length s} spart 1 Byte
Verkörperung der Ignoranz
3

MATL, 15 12 Bytes

3 Bytes gespart dank @Giuseppe

vin:"G@:)]Xh

Probieren Sie es bei MATL Online aus .

Aufgrund der Art und Weise, wie MATL die Ausgabe anzeigt, können Sie das leere Array im Zellenarray nicht explizit sehen. Hier ist eine Version, die die Ausgabe etwas expliziter zeigt.

Erläuterung

v       # Vertically concatenate the (empty) stack to create the array []
i       # Explicitly grab the input
n       # Compute the number of elements in the input (N)
:       # Create an array from [1, ..., N]
"       # Loop through this array
  G     # For each of these numbers, M
  @:    # Create an array from [1, ..., M]
  )     # Use this to index into the initial array
]       # End of the for loop
Xh      # Concatenate the entire stack into a cell array
Suever
quelle
Verwenden Sie vanstelle von []. Und nicht :verwendet 1als Standard erstes Argument? Dies könnte also vin:"G@:)]Xhfür 12 Bytes sein.
Giuseppe
@ Giuseppe Danke! Meine MATL ist ein wenig rostig, wie es scheint :(
Suever
2

Holzkohle , 6 Bytes

Eθ…θκθ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

 θ      Input array
E       Map over elements
   θ    Input array
  …     Moulded to length
    κ   Current loop index
        Implicitly print each array double-spaced
     θ  Input array
        Implicitly print

Es ist möglich, Charcoal zu einem Preis von 1 Byte aufzufordern, ein n+1-element-Array zu drucken, das die Eingabe als letztes Element enthält, aber die Ausgabe ist dieselbe, obwohl die Cursorposition anders wäre, wenn Sie dann etwas anderes drucken würden.

Neil
quelle
2

RAD , 7 Bytes

(⊂⍬),,\

Probieren Sie es online!

Dies funktioniert auch in Dyalog APL als Funktion.

Wie?

Dies funktioniert sowohl für APL als auch für RAD aufgrund ihrer engen Beziehung gleich.

  • (⊂⍬) das leere Array
  • , vorangestellt
  • ,\ die Präfixe (die das leere Array ausschließen)
Zacharý
quelle
2

Brainfuck , 43 Bytes

Nehmen Sie eine Liste von Nicht-Null-Zeichen als Eingabe und geben Sie alle Präfixe durch Zeilenumbruch getrennt zurück. Benötigt doppelt unendlich oder Wickelband.

,>-[+>,]<[-<]<<++++++++++[[<]>[.>]>[-<+>]<]

Probieren Sie es online!

user202729
quelle
Eine andere Antwort hat mich um mehr als die Hälfte übertroffen, weil ich beim Lesen nicht daran gedacht habe, die Ausgabe zu drucken . Natürlich funktioniert diese Methode nicht mit dem Drucken von aufsteigenden Suffixen.
User202729
40 Bytes mit etwas Neuordnung
Jo King
2

C # (Visual C # Interactive Compiler) , 39 Byte

x=>x.Select((_,i)=>x.Take(i)).Append(x)

Probieren Sie es online!

Dana
quelle
Sie müssen die Verwendung System.Linq; in Ihr bytecount aufnehmen. Und es scheint, dass ein Teil Ihrer Ausgabelogik in der Ausgabe der Arrays liegt. Da leeres Array nur leeres Array zurückgibt.
LiefdeWen
@LiefdeWen - da dieser Interpreter einen Verweis auf enthält System.Linq, muss ich diesen nicht in die Byteanzahl aufnehmen. Meine Einreichung würde als eine andere Sprache angesehen als sagen .NET Core. github.com/dotnet/roslyn/wiki/C%23-Interactive-Walkthrough - Sie erwähnen den Druck, der ein separates Problem darstellt. Ich möchte zunächst Klarheit darüber erlangen.
Dana
In Bezug auf das Drucken ist hier eine Version, die das Ergebnis im Grunde genommen auf der Konsole ablegt - tio.run/##XY29CsIwGEX3PEXGBGKhtVt/… - nicht ganz so sicher! Die Frage, die ich habe, ist, wann es akzeptabel ist, Arrayvs IListvs zu verwenden IEnumerable.
Dana
2

F # (Mono) , 45 Bytes

fun x->List.mapi(fun i y->List.take i x)x@[x]

Probieren Sie es online!

Ich bin mir nicht ganz sicher, ob dies gültig ist, aber es scheint, als ob es der gleichen "anonymen Lambda" -Syntax folgt, die ich anscheinend in mehreren anderen Sprachen verwendet habe.

Dana
quelle
2

Java 8+ , 86 77 Bytes

-9 Bytes dank Kevin Cruijssen ( Abschaffung des Imports)!

x->java.util.stream.IntStream.range(0,x.size()+1).mapToObj(t->x.subList(0,t))

Probieren Sie es online!

Alternative, 65 Bytes

Das Folgende wird die Ergebnisse auf stdout ausgeben (aufgrund von Olivier Grégoire ):

x->{for(int i=0;i<=x.size();)System.out.print(x.subList(0,i++));}

Probieren Sie es online aus

ბიმო
quelle
Sie können es zu 77 Bytes Golf spielen, indem Sie java.util.stream.IntStreamdirekt verwenden und den Import fallenlassen.
Kevin Cruijssen
@ KevinCruijssen: Oh, danke! Ich wusste nicht einmal, dass dies möglich ist, das ist sicherlich hilfreich (zumindest für Golfzwecke).
10.
x->{for(int i=0;i<=x.size();)System.out.println(x.subList(0,i++));}( 67 Bytes ). Dies wird gedruckt, anstatt Streams zu verwenden. Drucken ist normalerweise der kürzeste Weg, um komplexe Strukturen auszugeben.
Olivier Grégoire
@Oliviergrégoire: In dem Fall kommst du wohl mit durch System.out.print da die Ausgabe immer noch eindeutig ist.
ბიმო
@BMO Ja, das wäre möglich!
Olivier Grégoire
2

Brachylog , 9 Bytes

a₀ᶠ~b.hĖ∧

Probieren Sie es online!

Erläuterung

a₀ᶠ           Find all prefixes of the input
   ~b         Add an element at the beginning of that list of prefixes
      hĖ      This element is the empty list
     .  ∧     (the list with the additional empty list is the output)
Tödlich
quelle
2

Rubin , 31 29 Bytes

->a{[a*i=0]+a.map{a[0,i+=1]}}

Probieren Sie es online!

Erläuterung:

->a{             # take array input a
  [a*i=0]+       # set i to 0 and add whatever comes next to [[]] (a*0 == [])
  a.map{         # for every element in a (basically do a.length times)
    a[0,i+=1]  # increment i and return the first i-1 elements of a to map
  }
}
Asone Tuhid
quelle