Cette construction est une façon de représenter les nombres naturels.

Dans cette représentation, 0 est défini comme l'ensemble vide et pour tous les autres nombres, n est l'union de {0} et {n-1}.

Par exemple, pour construire 3, nous pouvons suivre l'algorithme:

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

Tâche

Comme vous l'avez peut-être deviné, votre tâche consiste à saisir un nombre naturel (y compris zéro) et à générer sa construction.

Vous pouvez sortir sous forme de chaîne ou d'objet set si la langue de votre choix prend en charge ces objets.

Si vous choisissez de sortir sous forme de chaîne, vous devez représenter un ensemble avec des accolades ( {}). Vous pouvez éventuellement représenter l'ensemble vide comme ø(sinon il doit s'agir d'un ensemble sans entrées {}). Vous pouvez également choisir d'ajouter des virgules et des espaces entre et après les entrées dans l'ensemble.

L'ordre n'est pas important, mais vous ne pouvez pas avoir d'éléments répétés dans les ensembles que vous produisez (par exemple {ø,ø})

C'est du code-golf donc le but est d'avoir le moins d'octets

Cas de test

Voici quelques cas de test avec quelques exemples de sorties.

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

Python , 28 octets

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

Essayez-le en ligne!

C'est une solution assez fade au problème. Pour les nombres supérieurs à zéro, vous pouvez obtenir la représentation avec la formule de chaîne "{{}"*x+"}"*x. Cependant, cela ne fonctionne pas pour zéro où il s'agit de la chaîne vide. Nous pouvons utiliser ce fait pour court-circuiter oret retourner l'ensemble vide.

Je voulais utiliser les objets set intégrés de python pour résoudre ce problème mais malheureusement:

TypeError: unhashable type: 'set'

Vous ne pouvez pas mettre d'ensembles à l'intérieur d'ensembles en python.

Haskell , 37 octets

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

Essayez-le en ligne!

Jusqu'à il y a 10 minutes, une réponse comme celle-ci n'aurait pas eu de sens pour moi. Tous les crédits vont à cette réponse de conseils .

Fondamentalement, nous utilisons >>as concat $ replicate(mais en lui passant une liste de n éléments au lieu de simplement n), et =<<as concatMap, répliquant ensuite n fois chacune des chaînes de la liste et concaténant le résultat en une seule chaîne.

Le 0cas est traité séparément car il retournerait une chaîne vide.

JavaScript, 28 octets

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

Représente les ensembles à l'aide de tableaux. Solution non récursive de 38 octets:

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

Renvoie les exemples de chaînes de sortie.

Mathematica, 27 octets

J'ai deux solutions à ce nombre d'octets:

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

Perl 6 , 37 octets

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

Essayez-le

Étendu:

{   # 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 octets

Code

ƒ)¯sÙ

Utilise l' encodage CP-1252 . Essayez-le en ligne!ou Vérifiez tous les cas de test! .

Explication

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

Rétine , 22 octets

.+
$*
\`.
{{}
{

^$
{}

Essayez-le en ligne!

Explication

.+
$*

Convertissez l'entrée en unaire.

\`.
{{}

Remplacez chaque chiffre unaire par {{}et imprimez le résultat sans retour à la ligne ( \).

{

Retirez les ouvertures {, afin que les autres }soient exactement ceux que nous devons encore imprimer pour fermer tous les ensembles. Cependant, la procédure ci-dessus échoue pour la saisie 0, où nous n'imprimerions rien. Donc...

^$
{}

Si la chaîne est vide, remplacez-la par l'ensemble vide.

Brain-Flak , 135 octets

Comprend +1 pour -A

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

Essayez-le en ligne!

(({}())<                 # 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 octets

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

CJam , 11 octets

Lri{]La|}*p

Imprime un objet de type ensemble composé de listes de listes. CJam imprime des listes vides sous forme de chaînes vides, car les listes et les chaînes sont presque interchangeables.

Essayez-le en ligne!

Explication

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

Ancienne réponse, 21 18 octets

C'était avant qu'il ne soit confirmé qu'il était correct d'imprimer une structure de liste imbriquée. Utilise l'algorithme de répétition de chaînes.

Sauvegardé 3 octets grâce à Martin Ender!

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

Explication

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.

Gelée , 6 octets

⁸,⁸Q$¡

Il s'agit d'un lien niladique qui lit un entier depuis STDIN et renvoie un tableau irrégulier.

Essayez-le en ligne!

Comment ça fonctionne

⁸,⁸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 octets

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

Pas le plus court chemin, mais je devais le faire avec récursivité.

Essayez-le en ligne!

Cardinal , 51 50 octets

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

Essayez-le en ligne!

Explication

%:#
x

Recevez l'entrée et envoyez vers le bas et à gauche du #

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

Imprimer "{" une fois puis imprimer "{} {" n-1 fois si n> 1 puis imprimer "{}" si n> 0

       #

v <8/ ?<
>  8\

Maintenez la valeur d'entrée jusqu'à la fin de la première boucle

v"}"<
>?-?^

Imprimer "}" une fois puis répéter n-1 fois si n> 1

AHK, 55 octets

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

Ce n'est pas la réponse la plus courte, mais j'ai apprécié cela parce que les particularités d'AutoHotkey font que cette méthode de récursion a l'air super fausse. Ifet les Loopinstructions supposent que la ligne suivante est la seule chose incluse si les crochets ne sont pas utilisés. Les accolades sont des caractères d'échappement, vous devez donc les échapper avec d'autres accolades pour les utiliser comme texte. De plus, la variable 1est le premier argument passé. Quand je lis le code sans connaître ces petits morceaux, la logique ressemble à ceci:

• Si 1 = 0, alors définissez ségal à la mauvaise réponse
• Boucle et ajoute un tas de crochets au début et quelques-uns à la fin à chaque fois
• Retournez en envoyant la chaîne résultante à la fenêtre courante

Sans tous les caractères d'échappement des crochets, cela ressemblerait à ceci:

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

JavaScript 50 octets

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

tinylisp , 52 octets

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

Essayez-le en ligne! (test harnais).

Explication

Notez que (cons x (cons y nil))c'est ainsi que vous créez une liste contenant xet yen 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 octets

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

Profitant d'une évaluation et d'une récursion des courts-circuits.

Essayez-le en ligne!

Pure Bash , 49 48 41 octets

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

Essayez-le en ligne!

dc , 46 octets

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

Essayez-le en ligne!

Entrée sur stdin, sortie sur stdout.

Cela fonctionne en calculant une formule pour la sortie souhaitée sous la forme d'un nombre de base 256. La commande P dans dc est ensuite utilisée pour imprimer le nombre base-256 sous forme de chaîne.

Plus d'explications:

Soit n l'entrée n. Le programme DC calcule la somme de

A = étage (256 ^ n / 255) * 125 (BF est interprété par dc comme 11 * 10 + 15 = 125)

et

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

Pour un:

Observez que 1 + 256 + 256 ^ 2 + ... + 256 ^ (n-1) est égal à (256 ^ n-1) / 255, par la formule d'une progression géométrique, et cela est égal au sol (256 ^ n / 255 ). C'est donc le nombre composé de n 1 en base 256.

Lorsque vous le multipliez par 125 pour obtenir A, le résultat est le nombre composé de n 125 en base 256 (125 est un chiffre unique en base 256, bien sûr). Il est probablement préférable d'écrire les chiffres de la base 256 sous forme de nombres hexadécimaux; 125 est hexadécimal 7D, donc A est le nombre de base 256 composé de n 7D dans une rangée.

B est similaire:

Cette fois, observez que 1 + 16777216 + 16777216 ^ 2 + ... + 16777216 ^ (n-1) est égal à (16777216 ^ n - 1) / 16777215, et cela est égal au plancher (16777216 ^ n / 16777215).

Maintenant, 256 ^ 3 = 16777216 et 8 ^ 8-1 = 16777215, c'est donc ce que nous calculons comme étage ((256 ^ n) ^ 3 / (8 ^ 8-1)).

D'après la représentation des séries géométriques, ce nombre dans la base 256 est 100100100 ... 1001 avec n des chiffres étant 1 et le reste des chiffres étant 0.

Ceci est multiplié par 8092541, qui est 7B7B7D en hexadécimal. Dans la base 256, il s'agit d'un nombre à trois chiffres composé des chiffres 7B, 7B et 7D (en écrivant ces chiffres en hexadécimal pour plus de commodité).

Il s'ensuit que le produit écrit en base 256 est un nombre à 3n chiffres composé des 3 chiffres 7B 7B 7D répétés n fois.

Celui-ci est multiplié par 256 ^ n, ce qui donne un nombre de base 256 à 4n chiffres, composé des 3 chiffres 7B 7B 7D répétés n fois, suivis de n 0. C'est B.

L'ajout de A + B donne maintenant le nombre de base 256 à 4 chiffres composé des 3 chiffres 7B 7B 7D répétés n fois, suivis de n 7D. Puisque 7B et 7D sont les codes ASCII pour {et }, respectivement, il s'agit de la chaîne composée de n copies de {{}suivi de n copies de} , ce qui est exactement ce que nous voulons pour n> 0. La commande P en dc imprime un nombre en base 256 comme une chaîne, comme nous en avons besoin.

Malheureusement, n = 0 doit être traité comme un cas spécial. Le calcul ci-dessus donne un résultat de 0 pour n = 0; dans ce cas, je viens de coder en dur l'impression de la chaîne {}.

Java 7, 61 octets

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

Essayez-le en ligne!

Lot, 88 octets

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

Brainf *** , 99 octets

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

(nouvelle ligne pour l'esthétique) Puisque c'est brainf ***, il prend l'entrée en tant que codes de caractères ascii (l'entrée "a" correspond à 96)

Braineasy, 60 octets

Aussi, dans ma langue personnalisée (basée sur brainf **, interprète ici ):

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

Vous devez coder en dur l'entrée du programme dans l'interpréteur parce que je suis paresseux.

05AB1E , 5 3 octets

F¯)

Essayez-le en ligne!

Cette version est après avoir précisé que les ensembles sont corrects.

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

Ancienne version (qui utilise le ø):

05AB1E , 5 4 octets

FX¸)

Essayez-le en ligne!

Où 1est équivalent à ø.

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.