Esta construção é uma maneira de representar os números naturais.

Nesta representação, 0 é definido como o conjunto vazio e, para todos os outros números, n é a união de {0} e {n-1}.

Por exemplo, para construir 3, podemos seguir o algoritmo:

3 =
{ø, 2} =
{ø, {ø, 1}} =
{ø, {ø, {ø}}}

Tarefa

Como você deve ter adivinhado, sua tarefa é coletar um número natural (incluindo zero) e produzir sua construção.

Você pode imprimir como uma sequência de caracteres ou como um objeto definido, se o seu idioma de escolha suportar esses objetos.

Se você escolher a saída como uma string, deverá representar um conjunto com chaves ( {}). Opcionalmente, você pode representar o conjunto vazio como ø(caso contrário, deve ser um conjunto sem entradas {}). Você também pode optar por adicionar vírgulas e espaços em branco entre e depois das entradas no conjunto.

A ordem não é importante, porém você pode não ter nenhum elemento repetido nos conjuntos que você produz (por exemplo {ø,ø})

Isso é código-golfe, então o objetivo é ter o menor número de bytes

Casos de teste

Aqui estão alguns casos de teste com alguns exemplos de saídas.

0 -> {}
1 -> {{}}
2 -> {{}{{}}}
3 -> {{}{{}{{}}}}
4 -> {{}{{}{{}{{}}}}}

Python , 28 bytes

lambda x:"{{}"*x+x*"}"or"{}"

Experimente online!

Esta é uma solução bastante branda para o problema. Para números maiores que zero, você pode obter a representação com a fórmula da string "{{}"*x+"}"*x. No entanto, isso não funciona para zero, onde esta é a string vazia. Podemos usar esse fato para causar um curto-circuito em umor e retornar o conjunto vazio.

Eu queria usar os objetos do conjunto interno do python para resolver esse problema, mas infelizmente:

TypeError: unhashable type: 'set'

Você não pode colocar conjuntos dentro de conjuntos em python.

Haskell , 37 bytes

f 0="{}"
f n=([1..n]>>)=<<["{{}","}"]

Experimente online!

Até 10 minutos atrás, uma resposta como essa não faria sentido para mim. Todos os créditos vão para esta resposta de dicas .

Basicamente, usamos >>como concat $ replicate(mas passando uma lista de n elementos em vez de simplesmente n) e =<<como concatMap, replicando n vezes cada uma das cadeias da lista e concatenando o resultado em uma única cadeia.

O 0caso é tratado separadamente, pois retornaria uma string vazia.

JavaScript, 28 bytes

f=n=>n?--n?[[],f(n)]:[[]]:[]

Representa conjuntos usando matrizes. Solução não recursiva de 38 bytes:

n=>'{{}'.repeat(n)+'}'.repeat(n)||'{}'

Retorna as seqüências de saída de exemplo.

Mathematica, 27 bytes

Eu tenho duas soluções nessa contagem de bytes:

Nest[{{}}~Union~{#}&,{},#]&
Union//@Nest[{{},#}&,{},#]&

Perl 6 , 37 bytes

{('{}','{{}}',{q:s'{{}$_}'}...*)[$_]}

Tente

Expandido:

{   # bare block lambda with implicit parameter ｢$_｣

  (
    # generate a sequence

    '{}',   # seed it with the first two values
    '{{}}',

    {   # bare block lambda with implicit parameter ｢$_｣

      q         # quote
      :scalar   # allow scalar values

      '{{}$_}'  # embed the previous value ｢$_｣ in a new string

    }

    ...         # keep using that code block to generate values

    *           # never stop

  )[ $_ ] # get the value at the given position in the sequence
}

05AB1E , 6 5 bytes

Código

ƒ)¯sÙ

Usa a codificação CP-1252 . Experimente online! ou Verifique todos os casos de teste!.

Explicação

ƒ       # For N in range(0, input + 1)..
 )      #   Wrap the entire stack into an array
  ¯     #   Push []
   s    #   Swap the two top elements
    Ù   #   Uniquify the array

Retina , 22 bytes

.+
$*
\`.
{{}
{

^$
{}

Experimente online!

Explicação

.+
$*

Converta a entrada para unário.

\`.
{{}

Substitua cada dígito unário por {{}e imprima o resultado sem avanço de linha à direita ( \).

{

Remova as aberturas {, para que as restantes }sejam exatamente as que ainda precisamos imprimir para fechar todos os conjuntos. No entanto, o procedimento acima falha na entrada 0, onde não imprimimos nada. Então...

^$
{}

Se a sequência estiver vazia, substitua-a pelo conjunto vazio.

Brain-Flak , 135 bytes

Inclui +1 para -A

(({}())<{({}[()]<((((((()()()()()){}){}){}())()){}{})>)}{}({}[()()])>)(({})<{({}[()]<(((({}()())[()()])))>)}{}>[()]){(<{}{}{}>)}{}{}{}

Experimente online!

(({}())<                 # Replace Input with input + 1 and save for later
  {({}[()]<              # For input .. 0
    (...)                # Push '}'
  >)}{}                  # End for and pop counter
  ({}[()()])             # change the top '}' to '{'. This helps the next stage
                         # and removes the extra '}' that we got from incrementing input
>)                       # Put the input back on

(({})<                   # Save input
  {({}[()]<              # For input .. 0
    (((({}()())[()()]))) # Replace the top '{' with "{{{}"
  >)}{}                  # end for and pop the counter
>[()])                   # Put down input - 1
{(<{}{}{}>)}             # If not 0, remove the extra "{{}"
{}{}{}                   # remove some more extras

Röda , 37 bytes

f n{[[[],f(n-1)]]if[n>1]else[[[]]*n]}

CJam , 11 bytes

Lri{]La|}*p

Imprime um objeto semelhante a um conjunto que consiste em listas de listas. O CJam imprime listas vazias como cadeias vazias, pois listas e cadeias são quase intercambiáveis.

Experimente online!

Explicação

L            Push an empty array 
 ri          Read an integer from input
   {    }*   Run this block that many times:
    ]          Wrap the entire stack in an array
     La        Wrap an empty list in an array, i.e. [[]]
       |       Set union of the two arrays
          p  Print the result

Resposta antiga, 21 18 bytes

Isso foi antes de se confirmar que não havia problema em imprimir uma estrutura de lista aninhada. Usa o algoritmo de repetição de string.

Economizou 3 bytes graças a Martin Ender!

ri{{}}`3/f*~_{{}}|

Explicação

ri                  Read an integer from input
  {{}}`             Push the string "{{}}"
       3/           Split it into length-3 subtrings, gives ["{{}" "}"]
         f*         Repeat each element of that array a number of times equal to the input
           ~_       Dump the array on the stack, duplicate the second element
             {{}}|  Pop the top element, if it's false, push an empty block, which gets 
                      printed as "{}". An input of 0 gives two empty strings on the 
                      repetition step. Since empty strings are falsy, we can correct the 
                      special case of 0 with this step.

Gelatina , 6 bytes

⁸,⁸Q$¡

Este é um link niládico que lê um número inteiro de STDIN e retorna uma matriz irregular.

Experimente online!

Como funciona

⁸,⁸Q$¡  Niladic link.

⁸       Set the return value to [].
    $   Combine the three links to the left into a monadic chain.
 ,⁸     Pair the previous return value with the empty array.
   Q    Unique; deduplicate the result.
     ¡  Read an integer n from STDIN and call the chain to the left n times.

Python 3 , 32 bytes

f=lambda n:[[],n and f(n-1)][:n]

Não é o caminho mais curto, mas eu apenas tive que fazer isso com recursão.

Experimente online!

Cardinal , 51 50 bytes

%:#>"{"#? v
x  ^?-"}{"<
v <8/ ?<
>  8\
v"}"<
>?-?^

Experimente online!

Explicação

%:#
x

Receba entrada e envie para baixo e para a esquerda a partir do #

   >"{" ? v
   ^?-"}{"<

Imprima "{" uma vez e depois imprima "{} {" n-1 vezes se n> 1 e imprima "{}" se n> 0

       #

v <8/ ?<
>  8\

Mantenha o valor de entrada até que o primeiro loop seja concluído

v"}"<
>?-?^

Imprima "}" uma vez e repita n-1 vezes se n> 1

AHK, 55 bytes

IfEqual,1,0
s={{}{}}
Loop,%1%
s={{ 2}{}}%s%{}}
Send,%s%

Não é a resposta mais curta, mas gostei disso porque as idiossincrasias do AutoHotkey fazem esse método de recursão parecer super errado. IfAs Loopinstruções e assumem que a próxima linha é a única coisa incluída se colchetes não forem usados. Parênteses curvos são caracteres de escape, portanto, você deve escapá-los com outros parênteses para usá-los como texto. Além disso, a variável 1é o primeiro argumento passado. Quando leio o código sem conhecer esses detalhes, a lógica fica assim:

• Se 1 = 0, defina sigual à resposta errada
• Faça um loop e adicione um monte de colchetes ao começo e alguns ao final toda vez
• Retorne enviando a sequência resultante para a janela atual

Sem todos os caracteres de escape do colchete, ficaria assim:

IfEqual,1,0
   s={}
Loop,%1%
   s={{}%s%}
Send,%s%

JavaScript 50 bytes

g=n=>n==0?"":"{{}"+g(n-1)+"}"
z=m=>m==0?"{}":g(m)

tinylisp , 52 bytes

(d f(q((n)(i n(i(e n 1)(c()())(c()(c(f(s n 1))())))(

Experimente online! (equipamento de teste).

Explicação

Observe que (cons x (cons y nil))é assim que você cria uma lista que contém xe yno Lisp.

(d f           Define f to be
 (q(           a quoted list of two items (which acts as a function):
  (n)           Arglist is a single argument n
  (i n          Function body: if n is truthy (i.e. nonzero)
   (i(e n 1)     then if n equals 1
    (c()())       then cons nil to nil, resulting in (())
    (c            else (if n > 1) cons
     ()            nil to
     (c            cons
      (f(s n 1))    (recursive call with n-1) to
      ())))         nil
   ()))))        else (if n is 0) nil

C (gcc) , 52 bytes

n(i){putchar(123);i>1&&n(0);i&&n(i-1);putchar(125);}

Aproveitando algumas avaliações e recursões de curto-circuito.

Experimente online!

Pure Bash , 49 48 41 bytes

for((;k++<$1;)){ s={{}$s};};echo ${s-{\}}

Experimente online!

dc , 46 bytes

[[{}]]sx256?^dd3^8d^1-/8092541**r255/BF*+d0=xP

Experimente online!

Entrada em stdin, saída em stdout.

Isso funciona calculando uma fórmula para a saída desejada como um número de base 256. O comando P em dc é usado para imprimir o número da base 256 como uma sequência.

Mais explicações:

Seja n a entrada n. O programa dc calcula a soma de

A = piso (256 ^ n / 255) * 125 (BF é interpretado por dc como 11 * 10 + 15 = 125)

e

B = piso ((256 ^ n) ^ 3 / (8 ^ 8-1)) * 8092541 * (256 ^ n).

Para:

Observe que 1 + 256 + 256 ^ 2 + ... + 256 ^ (n-1) é igual a (256 ^ n-1) / 255, pela fórmula de uma progressão geométrica, e isso é igual a piso (256 ^ n / 255 ) Portanto, este é o número que consiste em n 1 na base 256.

Quando você o multiplica por 125 para obter A, o resultado é o número que consiste em n 125 na base 256 (é claro que 125 é um dígito na base 256). Provavelmente é melhor escrever os dígitos na base 256 como números hexadecimais; 125 é hexadecimal 7D, então A é o número da base 256 que consiste em n 7Ds seguidos.

B é semelhante:

Desta vez, observe que 1 + 16777216 + 16777216 ^ 2 + ... + 16777216 ^ (n-1) é igual a (16777216 ^ n - 1) / 16777215, e isso é igual a piso (16777216 ^ n / 16777215).

Agora, 256 ^ 3 = 16777216 e 8 ^ 8-1 = 16777215, então é isso que estamos computando como piso ((256 ^ n) ^ 3 / (8 ^ 8-1)).

A partir da representação geométrica em série, esse número na base 256 é 100100100 ... 1001 com n dos dígitos sendo 1 e o restante dos dígitos sendo 0.

Isso é multiplicado por 8092541, que é 7B7B7D em hexadecimal. Na base 256, este é um número de três dígitos que consiste nos dígitos 7B, 7B e 7D (escrevendo esses dígitos em hexadecimal por conveniência).

Daqui resulta que o produto escrito na base 256 é um número de 3n dígitos que consiste nos 3 dígitos 7B 7B 7D repetidos n vezes.

Isso é multiplicado por 256 ^ n, resultando em um número base-256 de 4n dígitos, consistindo nos 3 dígitos 7B 7B 7D repetidos n vezes, seguidos por n 0's. Isso é B.

A adição de A + B agora gera o número base-256 de 4n dígitos, consistindo nos 3 dígitos 7B 7B 7D repetidos n vezes, seguidos por n 7D's. Como 7B e 7D são os códigos ASCII para {e} , respectivamente, essa é a sequência que consiste em n cópias de {{}seguidas por n cópias de }, que é exatamente o que queremos para n> 0. O comando P em dc imprime um número base-256 como uma corda, exatamente como precisamos.

Infelizmente, n = 0 deve ser tratado como um caso especial. O cálculo acima produz um resultado de 0 para n = 0; nesse caso, eu apenas codifiquei a impressão da string {}.

Java 7, 61 bytes

String p(int p){return p<1?"{}":p<2?"{{}}":"{{}"+p(p-1)+"}";}

Experimente online!

Lote, 88 bytes

@set s={}
@if %1 gtr 0 set s=&for /l %%i in (1,1,%1)do @call set s={{}%%s%%}
@echo %s%

Brainf *** , 99 bytes

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

(nova linha para a estética) Como é brainf ***, recebe a entrada como códigos de caracteres ascii (a entrada "a" corresponde a 96)

Braineasy, 60 bytes

Além disso, na minha linguagem personalizada (baseada em brainf **, intérprete aqui ):

#123#[->+>+<<]>++<,[[-<+<+>>]<[->>>..<.<<]<[->>>.<<<]!]>>.<.

Você precisa codificar a entrada do programa no intérprete porque sou preguiçoso.

05AB1E , 5 3 bytes

F¯)

Experimente online!

Esta versão é depois que ele esclareceu que os conjuntos estão bem.

F   # From 1 to input...
 ¯  # Push global array (default value is []).
  ) # Wrap stack to array.

Versão antiga (que faz uso do ø):

05AB1E , 5 4 bytes

FX¸)

Experimente online!

Onde 1é equivalente a ø.

F    # From 1 to input...
 X   # Push value in register X (default is 1).
  ¸  # Wrap pushed value into an array.
   ) # Wrap whole stack into an array.
     # Implicit loop end (-1 byte).
     # Implicit return.