Construção natural

27

Os números naturais, incluindo 0, são formalmente definidos como conjuntos, da seguinte maneira :

  • O número 0 é definido como o conjunto vazio, {}
  • Para n ≥ 0, o número n +1 é definido como n ∪ { n }.

Como conseqüência, n = {0, 1, ..., n -1}.

Os primeiros números, definidos por este procedimento, são:

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

Desafio

Dado n, produza sua representação como um conjunto.

Regras

A saída pode consistentemente usar qualquer suporte de caracteres, tais como {}, [], ()ou <>. Caracteres arbitrários (como 01) não são permitidos.

Em vez de uma vírgula como acima, o separador pode ser qualquer sinal de pontuação; ou pode ser inexistente.

Os espaços (não as novas linhas) podem ser incluídos de forma arbitrária e inconsistente.

Por exemplo, o número 2 com colchetes e ponto e vírgula como separador é [[]; [[]]], ou equivalente [ [ ]; [ [ ] ] ], ou mesmo[ [ ] ;[ []]]

A ordem na qual os elementos de um conjunto são especificados não importa. Então você pode usar qualquer ordem na representação. Por exemplo, estas são algumas saídas válidas para 3:

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

Você pode escrever um programa ou função . A saída pode ser uma sequência ou, se estiver usando uma função, você pode retornar uma lista ou matriz aninhada cuja representação de sequência esteja em conformidade com o acima.

Casos de teste

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

Respostas:

8

Gelatina , 3 bytes

Ḷ߀

Este é um link monádico. Experimente online!

Como funciona

Cada número natural é o conjunto de todos os números naturais anteriores, ou seja, n = {0,…, n-1} . Como não há números naturais anteriores a 0 , temos que 0 = {} .

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

Ḷ    Unlength; yield [0, ..., n-1].
 ߀  Recursively map this link over the range.
Dennis
fonte
3
"Unlength" Eu gosto das funções inversas de Jelly.
ETHproductions
1
Se estou entendendo corretamente, o comprimento é basicamente o intervalo [0, n)?
Downgoat 30/09/16
5
@Downgoat Está correto. Eu tento manter letras e letras com pontos abaixo como inversas laterais. Uma vez que ḶLé um no-op, o mnemônico é pouco. Há também unbinary, undecimal, unhalve, unsine, unarccosine, etc.
Dennis
1
Espera, unarccosina? Isso não seria apenas cosseno?
ETHproductions
@ETHproductions Yup. Não há C com ponto abaixo.
Dennis
18

Python 2, 26 bytes

f=lambda n:map(f,range(n))

Teste em Ideone .

Dennis
fonte
10

JavaScript (ES6), 32 bytes

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

Simples o suficiente.

ETHproductions
fonte
1
@Downgoat Eu acho que essa pode ser a primeira vez que usei .map()sem uma função de seta dentro :-)
ETHproductions
bem tecnicamente f é uma função de seta: P
Downgoat 30/09/16
@ETHproductions Sério? .map(Number)é um caso bastante comum.
Sebastian Simon
@Xufox Bom ponto, acho que fiz isso pelo menos uma vez.
ETHproductions
4
@Xufox Embora .map(e=>+e)seja mais curto, por um byte.
Conor O'Brien
7

Perl 6 , 16 bytes

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

Retorna estrutura de dados aninhada.

Exemplo:

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

Explicação:

{   # 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
fonte
Isto é ... impressionante.
Conor O'Brien
6

Ruby, 27 21 bytes

Eu sou novo no golfe rubi, mas aqui não vale nada. Obrigado à Jordânia por economizar 6 bytes!

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

Esta é uma função recursiva f(um proc, para ser específico) e recebe um argumento s. Ele mapeia o proc fmais0...s , que é o intervalo [0, s).

Conor O'Brien
fonte
Você pode substituir map{|e|f[e]}por map &f.
Jordânia
@ Jordan Wow, que bom!
Conor O'Brien
5

Haskell, 32 27 bytes

p n='{':(p=<<[0..n-1])++"}"

Experimente em Ideone.

Laikoni
fonte
4

CJam , 14 bytes

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

Experimente online!

Explicação

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

Em cada iteração, o bloco constrói a representação de um número a partir do número anterior. Para ilustrar, vamos considerar a segunda iteração, onde a representação do número 2é construída a partir da de 1, que é a string "[[]]".

  1. A pilha contém "[[]]"
  2. Após a declaração _(duplicada), ela contém "[[]]","[[]]"
  3. Após a declaração )(uncons), ela contém "[[]]","[[]" ,"]"
  4. Após a declaração @(girar), ela contém "[[]","]" ,"[[]]"
  5. Após a instrução \(swap), ela contém "[[]","[[]]" ,"]"
  6. Após a declaração ](empacotar na matriz), ela contém ["[[]" "[[]]" "]"], que seria exibida como a sequência "[[][[]]]".
Luis Mendo
fonte
4

Queijo Cheddar, 17 bytes

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

Recursão curta + Faixa curta + iteração curta = Um desafio em que o cheddar se sai muito bem

Não concorrente, 11 bytes

n f->|>n=>f

o => operador foi adicionado após o lançamento deste desafio, tornando esta resposta não competitiva.

Isso pode parecer confuso, mas deixe-me simplificá-lo:

n f -> |> n => f

basicamente né a entrada e fé a própria função. |>ngera [0, n) e =>mapeia isso f.

Downgoat
fonte
1
O não concorrente parece muito legal: D
Conor O'Brien
4

05AB1E , 8 7 bytes

)IF)©`®

Explicação

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

Experimente online!

Guardado 1 byte graças a Adnan.

Emigna
fonte
Menos de 2 minutos LOL
Luis Mendo
@LuisMendo I literalmente apenas conectado quando o desafio foi publicado :)
Emigna
Eu acredito que você pode remover o último colchete: p
Adnan
@Adnan: Opa. Eu não sei como eu perdi isso :)
Emigna
3

Pitão, 4 bytes

LyMb

Suíte de teste

L: Defina a função ycom entradab

yMb: ymapeado no intervalo0, 1, ..., b-1

Na entrada 0, esse mapa retorna []. Caso contrário, ele retornará ymapeado sobre todos os números até b.

isaacg
fonte
3

MATL , 13 bytes

Xhi:"tY:Xh]&D

Experimente online!

Explicação

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
fonte
2
Resposta muito inteligente
Suever 30/09/16
@ Obrigadoever! Muito tempo ...
Luis Mendo
3

Perl, 27 bytes

Inclui +1 para -p

Muitos métodos diferentes parecem terminar em 27 ou 28 bytes. por exemplo

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

O melhor que eu pude encontrar é

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

já que em perls mais antigos, você pode deixar o espaço antes do fore obter 26 bytes

Ton Hospel
fonte
3

Mathematica, 14 bytes

Array[#0,#,0]&
alefalpha
fonte
2

Mathematica, 31 bytes

Implementa diretamente a definição como uma lista aninhada. Usa uma função sem nome que se chama recursivamente usando #0.

If[#<1,{},Join[t=#0[#-1],{t}]]&
Greg Martin
fonte
4
Você pode economizar muito usando um operador de chamada, bem como Union, em vez de Join: ±0={};±n_:={t=±(n-1)}⋃t... No entanto, neste caso, é ainda mais curto para ir para uma solução iterativa:Nest[{#}⋃#&,{},#]&
Martin Ender
2

Retina , 24 18 bytes

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

Experimente online! (A primeira linha ativa um conjunto de testes separado por avanço de linha.)

Explicação

.+
$*1<>

Isso converte a entrada em unário e acrescenta <>, a representação de 0.

+`1<
<<$'

Aqui, o +indica que essa substituição deve ser executada em um loop até que a string pare de mudar. É mais fácil explicar isso, seguindo as etapas individuais que eu segui no golfe. Vamos com esta versão da substituição:

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

Isso corresponde à última 1representação unária da entrada restante (para removê-la e decrementar a entrada), bem como ao conteúdo da corrente definida no final. Em seguida, ele é substituído por um novo conjunto que contém o anterior e seu conteúdo. No entanto, podemos notar que $1é seguido por> ambos os casos e, portanto, podemos incluí-lo na própria captura e omiti-lo do padrão de substituição. Isso leva ao formulário

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

No entanto, agora podemos observar que (.*)apenas captura o sufixo da sequência depois 1<e até reinserimos esse sufixo no final com $1. Como a sintaxe de substituição nos fornece uma maneira de nos referirmos à parte de uma sequência após uma correspondência $', podemos simplesmente omitir essas duas partes e terminar com a versão usada na resposta:

1<
<<$'
Martin Ender
fonte
Tem certeza de que é Retina e não o idioma> <>? :-P
Luis Mendo
@LuisMendo Eu acho que poderia ter usado {}, mas <>é o único par que nunca precisa escapar, então eu pensei em ir com isso. ;)
Martin Ender
2

Subcarga , 14 bytes

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

Experimente online!

Os programas fullload underload não podem receber entrada por meio de nenhum de nossos métodos definidos, portanto, esta é uma função que recebe entrada da pilha como um numeral da igreja (a maneira normal de definir números inteiros no underload) e produz saída para a pilha como uma string .

Os (…)marcadores de agrupamento são necessários para tornar isso uma função (reutilizável) e não um trecho (apenas utilizável uma vez). O wrapper no link TIO chama a função em questão de forma destrutiva ^, mas pode ser reutilizada através da cópia e consumindo apenas uma das cópias ao chamá-la. Ele também fornece entrada para o programa (aqui (:*:*), ou seja, 4) e imprime a saída usandoS .

Explicação

A subcarga é surpreendentemente adequada para essa tarefa, como os tarpits de Turing, com primitivas úteis como "copiar" e "cercar parênteses". (De alguma forma, o Underload, normalmente uma linguagem muito detalhada, está superando o Mathematica, normalmente uma linguagem que vence devido a um enorme conjunto de componentes internos, através de componentes internos mais adequados!) Veja como o programa funciona:

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

A exponenciação da função efetivamente faz com que as etapas da função se repitam quantas vezes, assim, por exemplo, (:a*)³ seria (:a*:a*:a*). Essa é a maneira idiomática de escrever um loop que se repete um determinado número de vezes no Underload. (Você pode observar que isso ~^é descrito de duas maneiras diferentes acima; isso porque os números inteiros no Underload são definidos como exponenciação de função especializada para esse número inteiro; portanto, para fazer uma exponenciação de função, você simplesmente tenta executar um número inteiro como se fosse uma função. .)

ais523
fonte
2

APL (NARS), 15 caracteres, 30 bytes

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

teste:

  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
└∊────────────────────────────────────────────────────┘

Não sei se isso seria aceito ... Zilde está ⍬ aqui representa o conjunto vazio {} se eu quiser imprimir o elemento Zilde ou um elemento cheio de Zilde, e Zilde incluiu tudo o que aconteceu é imprimir nada ... então para ver Zilde é preciso definir uma função que eu chamo de o ( o←⎕fmt) eu não insiro na contagem porque o elemento e sua estrutura existem mesmo que o sistema não o imprima ... É possível se io for 0

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

poderia ser uma solução de 12 caracteres também ...

RosLuP
fonte
1

Braquilog , 14 bytes

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

Experimente online!

Explicação

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
fonte
1

GAP , 22 bytes

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

Por exemplo:

gap> f(3);                            
[ [  ], [ [  ] ], [ [  ], [ [  ] ] ] ]
Peneiradores cristãos
fonte
1

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

Ungolfed:

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

Teste (Na raquete {} é igual a () e a saída padrão é ()):

(f 4)

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

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

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

'()
'(())
'(() (()))
'(() (()) ((()) ()))
rnso
fonte
1

Lote, 74 bytes

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

Usa o fato de que cada resposta é igual à resposta anterior inserida em si após a liderança {. As primeiras saídas são as seguintes:

{}

{{}}

{{{}}{}}

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

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

{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}
Neil
fonte
Você pode postar um exemplo mostrando os formatos de entrada e saída?
Luis Mendo