Construcción natural

27

Los números naturales que incluyen 0 se definen formalmente como conjuntos, de la siguiente manera :

  • El número 0 se define como el conjunto vacío, {}
  • Para n ≥ 0, el número n +1 se define como n ∪ { n }.

Como consecuencia, n = {0, 1, ..., n -1}.

Los primeros números, definidos por este procedimiento, son:

  • 0 = {}
  • 1 = {{}}
  • 2 = {{}, {{}}}
  • 3 = {{}, {{}}, {{}, {{}}}}

Reto

Dado n, muestra su representación como un conjunto.

Reglas

La salida puede utilizar constantemente cualquier soporte de carácter tales como {}, [], ()o <>. Los caracteres arbitrarios (como 01) no están permitidos.

En lugar de una coma como la anterior, el separador puede ser cualquier signo de puntuación; o puede ser inexistente.

Los espacios (no las nuevas líneas) pueden incluirse de manera arbitraria e inconsistente.

Por ejemplo, el número 2 con corchetes y punto y coma como separador es [[]; [[]]], o equivalente [ [ ]; [ [ ] ] ], o incluso[ [ ] ;[ []]]

El orden en que se especifican los elementos de un conjunto no importa. Entonces puede usar cualquier orden en la representación. Por ejemplo, estos son algunos resultados válidos para 3:

{{},{{}},{{},{{}}}}
{{{}},{{},{{}}},{}}
{{{}},{{{}},{}},{}}

Puedes escribir un programa o función . La salida puede ser una cadena o, si usa una función, puede devolver una lista o matriz anidada cuya representación de cadena se ajusta a lo anterior.

Casos de prueba

0  ->  {}
1  ->  {{}}
2  ->  {{},{{}}}
3  ->  {{},{{}},{{},{{}}}}
4  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
5  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}
6  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}}
7  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}}}
Luis Mendo
fuente
Relacionado
Luis Mendo

Respuestas:

8

Jalea , 3 bytes

Ḷ߀

Este es un enlace monádico. Pruébalo en línea!

Cómo funciona

Cada número natural es el conjunto de todos los números naturales anteriores, es decir, n = {0, ..., n-1} . Como no hay números naturales que precedan a 0 , tenemos que 0 = {} .

Ḷ߀  Monadic link. Argument: n (natural number)

Ḷ    Unlength; yield [0, ..., n-1].
 ߀  Recursively map this link over the range.
Dennis
fuente
3
"Unlength" Me gustan las funciones inversas de Jelly.
ETHproductions
1
Si estoy entendiendo correctamente, ¿la longitud es básicamente el rango [0, n)?
Downgoat
55
@Downgoat Eso es correcto. Intento mantener letras y letras con un punto debajo como inversos laterales. Como ḶLes un no-op, la mnemónica es de longitud reducida. También hay unbinary, undecimal, unhalve, unsine, unarccosine, etc.
Dennis
1
Espera, ¿unarccosina? ¿No sería eso solo coseno?
ETHproductions
@ETHproductions Sí. Sin embargo, no hay C con el punto a continuación.
Dennis
10

JavaScript (ES6), 32 bytes

f=n=>[...Array(n).keys()].map(f)

Suficientemente simple.

ETHproducciones
fuente
1
@Downgoat Creo que esta puede ser la primera vez que uso .map()sin una función de flecha en el interior :-)
ETHproductions
bien técnicamente f es una función de flecha: P
Downgoat
@ETHproductions ¿En serio? .map(Number)Es un caso bastante común.
Sebastian Simon el
@Xufox Buen punto, creo que lo he hecho al menos una vez.
ETHproductions
44
@Xufox aunque .map(e=>+e)es más corto, por un byte.
Conor O'Brien el
7

Perl 6 , 16 bytes

{({@_}…*)[$_]}

Devuelve la estructura de datos anidados.

Ejemplo:

say {({@_}…*)[$_]}( 4 );
# [[] [[]] [[] [[]]] [[] [[]] [[] [[]]]]]

Explicación:

{   # lambda with implicit parameter 「$_」

  (


    # produce a lazy infinite sequence of all results

    {       # lambda with implicit parameter 「@_」
      @_    # array containing all previously seen values in the sequence
    }

           # keep repeating that block until:

    *       # Whatever ( never stop )


  )[ $_ ]   # use the outer block's argument to index into the sequence

}
Brad Gilbert b2gills
fuente
Esto es ... impresionante.
Conor O'Brien el
6

Rubí, 27 21 bytes

Soy nuevo en Ruby Golf, pero aquí no pasa nada. ¡Gracias a Jordan por guardar 6 bytes!

f=->s{(0...s).map &f}

Esta es una función recursiva f(un proceso, para ser específico) y toma un argumento s. Se asigna el proc fmás 0...s, que es el rango [0, s).

Conor O'Brien
fuente
Se puede reemplazar map{|e|f[e]}con map &f.
Jordania
@ Jordan Wow, bien!
Conor O'Brien
4

CJam , 14 bytes

"[]"{_)@\]}ri*

Pruébalo en línea!

Explicación

"[]"            e# Push this string. It is the representation of 0, and also serves
                e# to initialize
    {     }ri*  e# Repeat this block as many times as the input number
     _          e# Duplicate
      )         e# Uncons: split into array without the last element, and last element
       @\       e# Rotate, swap
         ]      e# Pack stack contents into an array
                e# Implicitly display

En cada iteración, el bloque construye la representación de un número a partir del anterior. Para ilustrar, consideremos la segunda iteración, donde la representación del número 2se construye a partir de la de 1, que es la cadena "[[]]".

  1. La pila contiene "[[]]"
  2. Después de la declaración _(duplicado) que contiene "[[]]","[[]]"
  3. Después de la declaración )(Subsi) que contiene "[[]]", "[[]","]"
  4. Después de la declaración @(girar) que contiene "[[]", "]","[[]]"
  5. Después de la declaración \(swap) que contiene "[[]", "[[]]","]"
  6. Después de la declaración ](paquete en matriz) que contiene ["[[]" "[[]]" "]"], que se mostrará como la cadena "[[][[]]]".
Luis Mendo
fuente
4

Cheddar, 17 bytes

n f->(|>n).map(f)

Recurrencia corta + Rango corto + iteración corta = Un desafío donde el cheddar funciona muy bien

No competidor, 11 bytes

n f->|>n=>f

El =>operador se agregó después de que se lanzó este desafío, lo que hace que esta respuesta no sea competitiva.

Esto puede parecer confuso, pero déjame simplificarlo:

n f -> |> n => f

Básicamente nes la entrada y fes la función misma. |>ngenera [0, n) y =>asigna eso encima f.

Downgoat
fuente
1
El que no compite se ve muy bien: D
Conor O'Brien
4

05AB1E , 8 7 bytes

)IF)©`®

Explicación

)         # wrap stack in a list, as stack is empty this becomes the empty list []
 IF       # input number of times do:
   )      # wrap stack in list
    ©     # store a copy of the list in the register
     `    # flatten the list
      ®   # push the copy from the register
          # implicitly print top value of stack after the last loop iteration

Pruébalo en línea!

Guardado 1 byte gracias a Adnan.

Emigna
fuente
Menos de 2 minutos LOL
Luis Mendo
@LuisMendo Literalmente me conecté cuando se publicó el desafío :)
Emigna
Creo que puedes eliminar el último paréntesis: p
Adnan
@Adnan: Vaya. No sé cómo me perdí eso :)
Emigna
3

Pyth, 4 bytes

LyMb

Banco de pruebas

L: Definir la función ycon entradab

yMb: ymapeado sobre el rango0, 1, ..., b-1

En la entrada 0, este mapa vuelve []. De lo contrario, vuelve ymapeado sobre todos los números hasta b.

isaacg
fuente
3

MATL , 13 bytes

Xhi:"tY:Xh]&D

Pruébalo en línea!

Explicación

Xh              % Concatenate the stack contents into cell array. Since the stack
                % is empty, this produces the empty cell array, {}
  i:"     ]     % Take input number. Repeat that many times
     t          % Duplicate the cell array that is at the top of the stack
      Y:        % Unbox it, i.e., push its contents onto the stack
        Xh      % Concatenate the stack contents into a cell array
           &D   % String representation. Implicitly display
Luis Mendo
fuente
2
Respuesta muy inteligente
Suever
@Suever ¡Gracias! Demasiado tiempo sin embargo ...
Luis Mendo
3

Perl, 27 bytes

Incluye +1 para -p

Muchos métodos diferentes parecen terminar en 27 o 28 bytes. p.ej

#!/usr/bin/perl -p
$\=$_="{@F}"for@F[0..$_]}{

Lo mejor que pude encontrar es

#!/usr/bin/perl -p
s/./{$_/ for($\="{}")x$_}{

ya que en perls más antiguos puedes soltar el espacio antes fory obtener 26 bytes

Ton Hospel
fuente
3

Mathematica, 14 bytes

Array[#0,#,0]&
alephalpha
fuente
2

Mathematica, 31 bytes

Implementa directamente la definición como una lista anidada. Utiliza una función sin nombre que recursivamente se llama a sí misma usando #0.

If[#<1,{},Join[t=#0[#-1],{t}]]&
Greg Martin
fuente
44
Puede ahorrar mucho utilizando un operador con nombre, así como en Unionlugar de Join: ±0={};±n_:={t=±(n-1)}⋃t... Sin embargo, en este caso es aún más corto buscar una solución iterativa:Nest[{#}⋃#&,{},#]&
Martin Ender
2

Retina , 24 18 bytes

.+
$*1<>
+`1<
<<$'

Pruébalo en línea! (La primera línea habilita un conjunto de pruebas separado por salto de línea).

Explicación

.+
$*1<>

Esto convierte la entrada a unario y agrega <>, la representación de 0.

+`1<
<<$'

Aquí, +indica que esta sustitución debe ejecutarse en un bucle hasta que la cadena deje de cambiar. Es más fácil explicar esto siguiendo los pasos individuales que tomé para jugar golf. Comencemos con esta versión de la sustitución:

1<(.*)>
<<$1>$1>

Esto coincide con la última 1representación unaria de la entrada restante (para eliminarla y disminuir la entrada), así como con el contenido del conjunto actual al final. Esto luego se reemplaza con un nuevo conjunto que contiene el anterior, así como su contenido. Sin embargo, podemos notar que $1es seguido >en ambos casos y, por lo tanto, podemos incluirlo en la captura misma y omitirlo del patrón de sustitución. Eso lleva a la forma

1<(.*)
<<$1$1

Sin embargo, ahora podemos observar que (.*)solo captura el sufijo de la cadena después 1<e incluso reinsertamos este sufijo al final con $1. Dado que la sintaxis de sustitución nos da una forma de referirnos a la parte de una cadena después de una coincidencia $', simplemente podemos omitir ambas partes y terminar con la versión utilizada en la respuesta:

1<
<<$'
Martin Ender
fuente
¿Estás seguro de que esto es Retina y no el idioma> <>? :-P
Luis Mendo
@LuisMendo Supongo que podría haberlo usado {}, pero <>es el único par que nunca necesita escapar, así que pensé en ir con eso. ;)
Martin Ender
2

Baja carga , 14 bytes

((:a*)~^()~^a)

Pruébalo en línea!

Los programas completos de subcarga no pueden recibir datos a través de ninguno de nuestros métodos definidos, por lo que esta es una función que toma datos de la pila como un número de Church (la forma normal de definir enteros en Underload) y produce una salida a la pila como una cadena .

Los (…)marcadores de agrupación son necesarios para que esto sea una función (reutilizable) en lugar de un fragmento (solo se puede usar una vez). El contenedor en el enlace TIO llama a la función en cuestión de manera destructiva ^, pero podría reutilizarse haciendo una copia y consumiendo solo una de las copias al llamarla. También proporciona entrada al programa (aquí (:*:*), es decir, 4), e imprime la salida usando S.

Explicación

La subcarga es sorprendentemente adecuada para esta tarea, ya que las carpas de Turing van, teniendo primitivas tan útiles como "copiar" y "rodear con paréntesis". (De alguna manera, Underload, normalmente un lenguaje muy detallado, está superando a Mathematica, normalmente un idioma que gana debido a que tiene un gran conjunto de builtins, a través de tener builtins más apropiados). Así es como funciona el programa:

((:a*)~^()~^a)
(            )   Make a snippet into a function
 (   )~^         Exponentiate the following function by the top of stack:
  :                Copy the top stack element
   a               Surround the copy in parentheses
    *              Append the copy to the original, popping the copy
          ~^     Run the resulting function, with the following argument on its stack:
        ()         Empty string
            a    Surround the result in parentheses

La exponenciación de la función hace que los pasos de la función se repitan muchas veces, por lo que, por ejemplo, (:a*)³ sería (:a*:a*:a*). Esa es la forma idiomática de escribir un bucle que se repite un número determinado de veces en Underload. (Puede observar que ~^se describe de dos maneras diferentes anteriormente; eso se debe a que los enteros en Underload se definen como exponenciación de funciones especializadas para ese entero, por lo que para hacer una exponenciación de funciones, simplemente intente ejecutar un entero como si fuera una función .)

ais523
fuente
2

APL (NARS), 15 caracteres, 30 bytes

{⍵=0:⍬⋄∇¨¯1+⍳⍵}

prueba:

  f←{⍵=0:⍬⋄∇¨¯1+⍳⍵}
  o←⎕fmt
  o f 0
┌0─┐
│ 0│
└~─┘
  o f 1
┌1───┐
│┌0─┐│
││ 0││
│└~─┘2
└∊───┘
  o f 2
┌2──────────┐
│┌0─┐ ┌1───┐│
││ 0│ │┌0─┐││
│└~─┘ ││ 0│││
│     │└~─┘2│
│     └∊───┘3
└∊──────────┘
  o f 3
┌3────────────────────────┐
│┌0─┐ ┌1───┐ ┌2──────────┐│
││ 0│ │┌0─┐│ │┌0─┐ ┌1───┐││
│└~─┘ ││ 0││ ││ 0│ │┌0─┐│││
│     │└~─┘2 │└~─┘ ││ 0││││
│     └∊───┘ │     │└~─┘2││
│            │     └∊───┘3│
│            └∊──────────┘4
└∊────────────────────────┘
  o f 4
┌4────────────────────────────────────────────────────┐
│┌0─┐ ┌1───┐ ┌2──────────┐ ┌3────────────────────────┐│
││ 0│ │┌0─┐│ │┌0─┐ ┌1───┐│ │┌0─┐ ┌1───┐ ┌2──────────┐││
│└~─┘ ││ 0││ ││ 0│ │┌0─┐││ ││ 0│ │┌0─┐│ │┌0─┐ ┌1───┐│││
│     │└~─┘2 │└~─┘ ││ 0│││ │└~─┘ ││ 0││ ││ 0│ │┌0─┐││││
│     └∊───┘ │     │└~─┘2│ │     │└~─┘2 │└~─┘ ││ 0│││││
│            │     └∊───┘3 │     └∊───┘ │     │└~─┘2│││
│            └∊──────────┘ │            │     └∊───┘3││
│                          │            └∊──────────┘4│
│                          └∊────────────────────────┘5
└∊────────────────────────────────────────────────────┘

No sé si esto sería aceptado ... Zilde está ⍬ aquí representa el conjunto vacío {} si quiero imprimir el elemento Zilde o un elemento lleno de Zilde, y Zilde adjuntó todo lo que sucede es imprimir nada ... así que para ver Zilde, uno tiene que definir una función. Lo llamo o ( o←⎕fmt). No inserto en el conteo porque el elemento y su estructura existen incluso si el sistema no lo imprime ... Es posible si io es 0

{⍵=0:⍬⋄∇¨⍳⍵}

podría ser una solución de 12 caracteres también ...

RosLuP
fuente
1

Brachylog , 14 bytes

yk:{,[]:?:gi}a

Pruébalo en línea!

Explicación

yk                The range [0, ..., Input - 1]
  :{        }a    Apply on each element of the range
    ,[]:?:gi      Group the empty list [] in a list Input times
Fatalizar
fuente
1

GAP , 22 bytes

f:=n->Set([0..n-1],f);

Por ejemplo:

gap> f(3);                            
[ [  ], [ [  ] ], [ [  ], [ [  ] ] ] ]
Christian Sievers
fuente
1

Raqueta 119 bytes

(λ(n)(define ll(list'()))(for((i(range 1 n)))(set! ll(cons ll(for/list((j(length ll)))(list-ref ll j)))))(reverse ll))

Sin golf:

(define f
  (λ (n)
    (define ll (list '()))
    (for ((i (range 1 n)))
      (set! ll
            (cons ll
                  (for/list ((j (length ll)))
                    (list-ref ll j)
                    ))))
    (reverse ll)))

Prueba (En Racket {} es igual que () y la salida predeterminada es ()):

(f 4)

'(() (()) ((()) ()) (((()) ()) (()) ()))

Para ver claramente cada número (0 a 3):

(for((i (f 4)))  (println (reverse i)))

'()
'(())
'(() (()))
'(() (()) ((()) ()))
rnso
fuente
1

Lote, 74 bytes

@set s={}
@for /l %%i in (1,1,%1)do @call set s={%%s%%%%s:~1%%
@echo %s%

Utiliza el hecho de que cada respuesta es igual a la respuesta anterior insertada en sí misma después de la guía {. Las primeras salidas son las siguientes:

{}

{{}}

{{{}}{}}

{{{{}}{}}{{}}{}}

{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}

{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}
Neil
fuente
¿Puedes publicar un ejemplo que muestre los formatos de entrada y salida?
Luis Mendo