P Pr Pref Prefi Prefijo Prefijo Prefijos

34

Dada una lista finita, devuelva una lista de todos sus prefijos, incluida una lista vacía, en orden ascendente de su longitud.

(Básicamente implementando la función Haskell inits).

Detalles

  • La lista de entrada contiene números (u otro tipo si es más conveniente).
  • El resultado debe ser una lista de listas .
  • El envío puede, pero no tiene que ser una función, se puede usar cualquier E / S predeterminada .
  • Hay una respuesta CW para todas las soluciones triviales .

Ejemplo

[] -> [[]]
[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]]
falla
fuente
Si un idioma no define ningún tipo, excepto los caracteres, ¿puedo tomar la entrada como una cadena y separar la entrada por nuevas líneas, en el caso de un programa completo?
NieDzejkob
@NieDzejkob No estoy seguro de qué consenso hay para este caso, pero la respuesta Brainfuck parece hacer algo así.
defecto
¿Podemos esperar que la lista sea nula?
Es especialmente común en C / C ++, el uso principal son las cadenas.
@Rogem Si es tan común, creo que permitirlo es razonable.
falla

Respuestas:

15

Haskell , 20 bytes

Editar: Sin embargo, un byte más corto con un escaneo completamente diferente.

Una función anónima que supera ligeramente la importación trivial.

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

Pruébalo en línea!

  • Usos =<<para la abreviatura (scanr(\_->init)=<<id) l = scanr(\_->init) l l.
  • Escanea una lista lde derecha a izquierda, recogiendo resultados intermedios con la función \_->init.
  • Esa función ignora los elementos escaneados (solo se usan para obtener la longitud total correcta para los resultados recopilados), por lo que realmente se repite aplicando inital valor inicial del escaneo, que también es l.
Ørjan Johansen
fuente
13

brainfuck , 21 12 bytes

-9 bytes gracias a Arnauld que sugiere el separador en ÿlugar de las nuevas líneas

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

Pruébalo en línea!

Toma bytes a través de STDIN sin bytes nulos e imprime una serie de prefijos separados por el ÿcarácter con un ÿcarácter inicial . Por ejemplo, para la entrada Prefixes, la salida es ÿÿPÿPrÿPreÿPrefÿPrefiÿPrefixÿPrefixeÿPrefixes.

Para facilitar la lectura, aquí hay una versión con nuevas líneas .

Explicación:

-              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
Jo King
fuente
1
Esto solo funciona en implementaciones BF con celdas de ajuste de 8 bits sin signo.
Dev
11

JavaScript (ES6), 33 bytes

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

Pruébalo en línea!

¿Cómo?

+--- 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
fuente
wow, ese es un nivel completamente nuevo de explicación de código, trabajo increíble: O
Brian H.
@BrianH. ¡Gracias! Las tareas simples son buenas oportunidades para escribir explicaciones detalladas que no se pueden mencionar en un código más denso.
Arnauld
¿Lo hiciste a mano? o recibiste ayuda de algún software extraño del que nunca he oído hablar?
Brian H.
2
Solo Notepad ++ con alguna edición en modo columna .
Arnauld
6

Jalea , 3 bytes

ṭṖƤ

Pruébalo en línea!

Cómo funciona

ṭṖƤ  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
fuente
6

Japt , 4 bytes

²£¯Y

Pruébalo en línea!

Explicación:

²       :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
fuente
6

Perl 6 , 13 bytes

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

Pruébalo en línea!

Para explicar:

En Perl 6 se puede envolver un operador entre corchetes como una forma alternativa de escribir una reducción de la lista. [+] @arrayDevuelve la suma de los elementos @array, [*] @arrayretorna el producto, etc. También puede preceder al operador con una barra invertida para hacer una reducción "triangular", que algunas lenguas llaman "exploración". Así que [\+] @arraydevuelve una lista que consiste en el primer elemento de@array , luego la suma de los dos primeros elementos, luego la suma de los primeros tres elementos, etc.

Aquí [\,] @_hay una reducción triangular sobre la matriz de entrada @_utilizando el operador de construcción de lista ,. Por lo tanto, se evalúa en una lista de listas: el primer elemento de @_, los dos primeros elementos de @_, etc. Eso es casi lo que se necesita, pero el problema requiere primero una lista vacía. Entonces, el primer elemento de la lista de retorno es una lista literalmente vacía (),, luego la reducción sobre la lista de entrada se aplana con el resto de la lista de retorno |.

Sean
fuente
2
O_o lo que está pasando aquí
solo ASCII
1
@ Reducción triangular
usuario202729
5

R , 40 39 bytes

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

Pruébalo en línea!

-1 byte gracias a digEmAll

La salida del listtipo de R es un poco extraña; utiliza indexación secuencial, por ejemplo, la salida para

list(1,2) es

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

En cambio, tomar la entrada como un vector proporciona un formato de salida más ordenado, aunque las entradas no son técnicamente lists.

Giuseppe
fuente
1
39 usando lapply
digEmAll
@digEmAll gracias!
Giuseppe
4

Mathematica 22 21 bytes

-1 byte gracias a Misha Lavrov !

{}~FoldList@Append~#&

Pura función. Toma una lista como entrada y devuelve una lista de listas como salida. Creo que esta es la solución más corta posible.

LegionMammal978
fuente
Podemos escribir la misma solución de forma más compacta que {}~FoldList@Append~#&.
Misha Lavrov
@MishaLavrov ¡Gracias! No pensé en usar la forma de argumento 1 + 2 al curry así.
LegionMammal978
3

PowerShell , 65 bytes

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

Pruébalo en línea!

PowerShell desenrolla útilmente listas de listas cuando Write-Outputocurre el valor predeterminado al finalizar el programa, por lo que obtiene un elemento por línea. Tack en un-join',' para ver mejor la lista de listas, convirtiendo las listas internas en cadenas.

(Ab) utiliza el hecho de que intentar generar una matriz vacía (por ejemplo, @()) no produce ninguna salida, por lo que una entrada de matriz vacía solo tiene ''como salida, ya que no $a[0..$_]dará como resultado nada. También arrojará algunos mensajes de error espectaculares.

AdmBorkBork
fuente
Envolverlo en parens en lugar de asignarlo ahorra 20 bytes . A menos que no pienses que eso cuenta como devolver una lista de listas. Siempre he sido borroso en esa distinción.
Veskah
@veskah Sí, eso es casi lo que tenía antes de editar esta versión. El problema con su solución o mi solución anterior: no devuelve una lista de listas. TIO1 vs TIO2
AdmBorkBork
3

K (ngn / k) , 8 bytes

,\(,!0),

Pruébalo en línea!

ngn
fuente
1
Esto es una especie de vudú. ,\(,()),en K4. ¿Unirse a nulo alistado a lo largo de la entrada alistada? ¿Cómo funciona?
Callejero
1
@streetster () es una lista vacía. (,()),xlo antepone x. finalmente ,\ hace un escaneo concat. el xse omite para formar una composición. tenga en cuenta que el final ,es diádico, por lo que es "concat", no "enlist".
ngn
1
@streetster en k4 puede ser un byte más corto: 1_',\0,pero mi programa de análisis no es lo suficientemente inteligente como para manejar esto ...
NGN
3

Lisp común , 39 bytes

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

Pruébalo en línea!

Explicación

(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
Solo ASCII
fuente
3

F #, 53 bytes

De hecho, tengo dos respuestas bastante similares para esto, ambas de la misma longitud. Ambos toman una secuencia genéricas como parámetro.

Primera solución

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

Pruébalo en línea!

Seq.take toma el primero n elementos de la secuencia. Seq.initcrea una nueva secuencia con un recuento (en este caso) de la longitud de la secuencia smás 1, y para cada elemento de la secuencia toma los primeros nelementos ens .

Segunda solución:

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

Similar a antes, excepto que crea una secuencia de 0 a la longitud de s . Luego toma esa cantidad de elementos de s.

¡Prueba esto en línea también!

Ciaran_McCarthy
fuente
fun s->Seq.map(fun n->Seq.take n s){0..Seq.length s} ahorra 1 byte
Encarnación de la ignorancia
3

MATL, 15 12 bytes

3 bytes guardados gracias a @Giuseppe

vin:"G@:)]Xh

Pruébalo en MATL Online .

Debido a la forma en que MATL muestra la salida, no puede ver explícitamente la matriz vacía en la matriz de celdas. aquí hay una versión que muestra la salida un poco más explícitamente.

Explicación

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
fuente
usar en vlugar de []. ¿Y no se :usa 1como primer argumento predeterminado? Entonces esto podría ser vin:"G@:)]Xhpor 12 bytes.
Giuseppe
@Giuseppe Gracias! Parece que mi MATL está un poco oxidado :(
Suever
3

SWI PROLOG 22 bytes

i(X,Y):-append(X,_,Y).

mosca de espuma de poliestireno
fuente
2

Carbón de leña , 6 bytes

Eθ…θκθ

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

 θ      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 posible, a un costo de 1 byte, pedirle a Charcoal que imprima una n+1matriz de elementos que incluye la entrada como su último elemento, pero la salida es la misma, aunque la posición del cursor sería diferente si luego imprimiera algo más.

Neil
fuente
2

RAD , 7 bytes

(⊂⍬),,\

Pruébalo en línea!

Esto también funciona en Dyalog APL como una función.

¿Cómo?

Esto funciona igual para APL y RAD, dada su estrecha relación.

  • (⊂⍬) la matriz vacía
  • , antepuesto a
  • ,\ los prefijos (que excluyen la matriz vacía).
Zacharý
fuente
2

Groovy , 37 bytes

{x->(0..x.size()).collect{x[0..<it]}}

Pruébalo en línea!

GolfIsAGoodWalkSpoilt
fuente
{it.inits().reverse()}funcionará una vez que tengamos un maravilloso 2.5 en TIO
solo ASCII el
2

brainfuck , 43 bytes

Tome una lista de caracteres no nulos como entrada y devuelva todos los prefijos separados por nueva línea. Requiere doble infinito o cinta de envoltura.

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

Pruébalo en línea!

usuario202729
fuente
Otra respuesta me superó en más de la mitad, porque no pensé en imprimir resultados mientras leía. Por supuesto, ese método no funcionará con la impresión de sufijos crecientes.
user202729
40 bytes con un poco de reorganización
Jo King
2

C # (compilador interactivo de Visual C #) , 39 bytes

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

Pruébalo en línea!

dana
fuente
System.Linq; Debe incluir el uso en su bytecount. Y parece que parte de su lógica de salida está en la salida de las matrices. Porque una matriz vacía solo devuelve una matriz vacía.
LiefdeWen
@LiefdeWen: entiendo que, dado que este intérprete incluye una referencia System.Linq, no tengo que incluir esto en el recuento de bytes. Mi presentación se consideraría un idioma diferente al de decir .NET Core. github.com/dotnet/roslyn/wiki/C%23-Interactive-Walkthrough - Menciona la impresión, que es un tema separado, me gustaría obtener claridad sobre esto primero.
dana
Con respecto a la impresión, aquí hay una versión que básicamente arroja el resultado a la consola: tio.run/##XY29CsIwGEX3PEXGBGKhtVt/… , ¡no es tan seguro! La pregunta que tengo es cuando es aceptable el uso Arrayvs IListvs IEnumerable.
dana
2

F # (Mono) , 45 bytes

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

Pruébalo en línea!

No estoy totalmente seguro de si esto es válido, pero parece que sigue la misma sintaxis "lambda anónima" que he usado en varios otros idiomas.

dana
fuente
2

Java 8+ , 86 77 bytes

-9 bytes gracias a Kevin Cruijssen (deshacerse de la importación)!

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

Pruébalo en línea!

Alternativa, 65 bytes

Lo siguiente imprimirá los resultados en stdout (debido a Olivier Grégoire ):

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

Pruébalo en línea

ბიმო
fuente
Puede jugar golf a 77 bytes simplemente usando java.util.stream.IntStreamdirectamente y soltando la importación.
Kevin Cruijssen
@KevinCruijssen: ¡Oh, gracias! Ni siquiera sabía que esto era posible, eso es ciertamente útil (al menos para fines de golf).
ბიმო
x->{for(int i=0;i<=x.size();)System.out.println(x.subList(0,i++));}( 67 bytes ). Esto se imprime en lugar de usar secuencias. La impresión suele ser la forma más corta de generar estructuras complejas.
Olivier Grégoire
@ OlivierGrégoire: en ese caso, probablemente pueda salirse con la suya System.out.printya que la salida aún no es ambigua.
ბიმო
@BMO De hecho, ¡eso sería posible!
Olivier Grégoire
2

Brachylog , 9 bytes

a₀ᶠ~b.hĖ∧

Pruébalo en línea!

Explicación

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)
Fatalizar
fuente
2

Ruby , 31 29 bytes

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

Pruébalo en línea!

Explicación:

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