Construction naturelle

27

Les nombres naturels dont 0 sont formellement définis comme des ensembles, de la manière suivante :

  • Le numéro 0 est défini comme l'ensemble vide, {}
  • Pour n ≥ 0, le nombre n +1 est défini comme n ∪ { n }.

En conséquence, n = {0, 1, ..., n -1}.

Les premiers nombres, définis par cette procédure, sont:

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

Défi

Étant donné n, affichez sa représentation sous forme d'ensemble.

Règles

La sortie peut toujours utiliser un support de caractère tels que {}, [], ()ou <>. Les caractères arbitraires (tels que 01) ne sont pas autorisés.

Au lieu d'une virgule comme ci-dessus, le séparateur peut être n'importe quel signe de ponctuation; ou il peut être inexistant.

Les espaces (pas les nouvelles lignes) peuvent être inclus de manière arbitraire et incohérente.

Par exemple, le numéro 2 avec des crochets et un point-virgule comme séparateur est [[]; [[]]], ou de manière équivalente [ [ ]; [ [ ] ] ], ou même[ [ ] ;[ []]]

L' ordre dans lequel les éléments d'un ensemble sont spécifiés n'a pas d'importance. Vous pouvez donc utiliser n'importe quel ordre dans la représentation. Par exemple, voici quelques sorties valides pour 3:

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

Vous pouvez écrire un programme ou une fonction . La sortie peut être une chaîne ou, si vous utilisez une fonction, vous pouvez renvoyer une liste ou un tableau imbriqué dont la représentation sous forme de chaîne est conforme à ce qui précède.

Cas de test

0  ->  {}
1  ->  {{}}
2  ->  {{},{{}}}
3  ->  {{},{{}},{{},{{}}}}
4  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
5  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}
6  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}}
7  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}}}
Luis Mendo
la source
En relation
Luis Mendo

Réponses:

8

Gelée , 3 octets

Ḷ߀

Ceci est un lien monadique. Essayez-le en ligne!

Comment ça marche

Chaque nombre naturel est l'ensemble de tous les nombres naturels précédents, c'est-à-dire n = {0,…, n-1} . Puisqu'il n'y a pas de nombres naturels précédant 0 , nous avons que 0 = {} .

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

Ḷ    Unlength; yield [0, ..., n-1].
 ߀  Recursively map this link over the range.
Dennis
la source
3
"Unlength" J'aime les fonctions inverses de Jelly.
ETHproductions
1
Si je comprends bien, la longueur est fondamentalement la plage [0, n)?
Downgoat
5
@Downgoat C'est exact. J'essaie de garder les lettres et les lettres avec un point en dessous comme inverses latérales. Puisqu'il ḶLs'agit d'un no-op, le mnémonique n'est pas de longueur. Il y a aussi non binaire, non décimal, unhalve, unine, unarccosine, etc.
Dennis
1
Attendez, unarccosine? Ne serait-ce pas simplement du cosinus?
ETHproductions
@ETHproductions Yup. Il n'y a pas de C avec un point en dessous cependant.
Dennis
18

Python 2, 26 octets

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

Testez-le sur Ideone .

Dennis
la source
10

JavaScript (ES6), 32 octets

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

Assez simple.

ETHproductions
la source
1
@Downgoat Je pense que c'est peut-être la première fois que j'utilise .map()sans fonction de flèche à l'intérieur :-)
ETHproductions
bien techniquement f est une fonction de flèche: P
Downgoat
@ETHproductions Vraiment? .map(Number)est un cas assez courant.
Sebastian Simon
@Xufox Bon point, je pense que je l'ai fait au moins une fois.
ETHproductions
4
@Xufox Bien qu'il .map(e=>+e)soit plus court, d'un octet.
Conor O'Brien
7

Perl 6 , 16 octets

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

Renvoie la structure de données imbriquée.

Exemple:

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

Explication:

{   # 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
la source
C'est ... impressionnant.
Conor O'Brien
6

Rubis, 27 21 octets

Je suis nouveau au golf rubis, mais ici, rien ne va. Merci à Jordan d'avoir économisé 6 octets!

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

Il s'agit d'une fonction récursive f(un proc, pour être spécifique) et prend un argument s. Il mappe le proc fsur 0...s, qui est la plage [0, s).

Conor O'Brien
la source
Vous pouvez remplacer map{|e|f[e]}par map &f.
Jordan
@ Jordan Wow, sympa!
Conor O'Brien
4

CJam , 14 octets

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

Essayez-le en ligne!

Explication

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

A chaque itération, le bloc construit la représentation d'un nombre à partir de celui du précédent. Pour illustrer, considérons la deuxième itération, où la représentation du nombre 2est construite à partir de celle de 1, qui est la chaîne "[[]]".

  1. La pile contient "[[]]"
  2. Après la déclaration _(en double) qu'il contient "[[]]","[[]]"
  3. AFTER )(uncons) contient "[[]]", "[[]","]"
  4. Après la déclaration @(rotate) il contient "[[]", "]","[[]]"
  5. Après la déclaration \(swap) qu'il contient "[[]","[[]]" ,"]"
  6. Après l'instruction ](pack dans le tableau) qu'elle contient ["[[]" "[[]]" "]"], qui serait affichée comme chaîne "[[][[]]]".
Luis Mendo
la source
4

Cheddar, 17 octets

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

Récursion courte + courte portée + courte itération = un défi où le cheddar fait très bien

Non concurrent, 11 octets

n f->|>n=>f

le => opérateur a été ajouté après la publication de ce défi, ce qui rend cette réponse non concurrentielle.

Cela peut sembler déroutant, mais permettez-moi de le simplifier:

n f -> |> n => f

nest essentiellement l'entrée et fest la fonction elle-même. |>ngénère [0, n) et les =>mappe f.

Downgoat
la source
1
Celui qui n'est pas en compétition a l'air très sympa: D
Conor O'Brien
4

05AB1E , 8 7 octets

)IF)©`®

Explication

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

Essayez-le en ligne!

Enregistré 1 octet grâce à Adnan.

Emigna
la source
Moins de 2 minutes LOL
Luis Mendo
@LuisMendo Je me suis littéralement connecté lorsque le défi a été publié :)
Emigna
Je pense que vous pouvez supprimer le dernier crochet: p
Adnan
@Adnan: Oups. Je ne sais pas comment j'ai raté ça :)
Emigna
3

Pyth, 4 octets

LyMb

Suite de tests

L: Définir la fonction yavec entréeb

yMb: ycartographié sur la plage0, 1, ..., b-1

Sur l'entrée 0, cette carte revient []. Sinon, il renvoie ymappé sur tous les nombres jusqu'à b.

isaacg
la source
3

MATL , 13 octets

Xhi:"tY:Xh]&D

Essayez-le en ligne!

Explication

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
la source
2
Réponse très intelligente
Suever
@Suever Merci! Bien trop long cependant ...
Luis Mendo
3

Perl, 27 octets

Comprend +1 pour -p

De nombreuses méthodes différentes semblent finir par 27 ou 28 octets. par exemple

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

Le mieux que j'ai pu trouver est

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

car sur les anciennes perles, vous pouvez supprimer l'espace avant le foret obtenir 26 octets

Ton Hospel
la source
3

Mathematica, 14 octets

Array[#0,#,0]&
alephalpha
la source
2

Mathematica, 31 octets

Implémente directement la définition en tant que liste imbriquée. Utilise une fonction sans nom qui s'appelle récursivement en utilisant #0.

If[#<1,{},Join[t=#0[#-1],{t}]]&
Greg Martin
la source
4
Vous pouvez économiser beaucoup en utilisant un opérateur nommé ainsi qu'au Unionlieu de Join: ±0={};±n_:={t=±(n-1)}⋃t... Cependant, dans ce cas, il est encore plus court d'opter pour une solution itérative:Nest[{#}⋃#&,{},#]&
Martin Ender
2

Rétine , 24 18 octets

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

Essayez-le en ligne! (La première ligne active une suite de tests séparés par un saut de ligne.)

Explication

.+
$*1<>

Cela convertit l'entrée en unaire et ajoute <>la représentation de 0.

+`1<
<<$'

Ici, le +indique que cette substitution doit être exécutée en boucle jusqu'à ce que la chaîne cesse de changer. Il est plus facile d'expliquer cela en passant par les étapes individuelles que j'ai suivies en jouant au golf. Voyons avec cette version de la substitution:

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

Cela correspond à la dernière 1représentation unaire de l'entrée restante (pour la supprimer et décrémenter l'entrée), ainsi qu'au contenu de l'ensemble actuel à la fin. Celui-ci est alors remplacé par un nouvel ensemble contenant le précédent ainsi que son contenu. Cependant, nous pouvons remarquer que $1c'est suivi >dans les deux cas et donc nous pouvons l'inclure dans la capture elle-même et l'omettre du modèle de substitution. Cela mène au formulaire

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

Cependant, nous pouvons maintenant observer que (.*)capture juste le suffixe de la chaîne après 1<et nous réinsérons même ce suffixe à la fin avec $1. Étant donné que la syntaxe de substitution nous donne un moyen de faire référence à la partie d'une chaîne après une correspondance avec, $'nous pouvons simplement omettre ces deux parties et nous retrouver avec la version utilisée dans la réponse:

1<
<<$'
Martin Ender
la source
Vous êtes sûr qu'il s'agit de la rétine et non de la langue> <>? :-P
Luis Mendo
@LuisMendo Je suppose que j'aurais pu utiliser {}, mais <>c'est la seule paire qui n'a jamais besoin de s'échapper, alors j'ai pensé que j'irais avec ça. ;)
Martin Ender
2

Sous-charge , 14 octets

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

Essayez-le en ligne!

Les programmes complets de sous-charge ne peuvent pas prendre d'entrée via l'une de nos méthodes définies, il s'agit donc d'une fonction qui prend l'entrée de la pile comme un nombre Church (la façon normale de définir des entiers dans Underload), et produit une sortie vers la pile sous forme de chaîne .

Les (…)marqueurs de regroupement sont nécessaires pour en faire une fonction (réutilisable) plutôt qu'un extrait de code (utilisable une seule fois). L'encapsuleur dans le lien TIO appelle la fonction en question en utilisant destructivement ^, mais il pourrait être réutilisé en faisant une copie de celui-ci et en ne consommant qu'une des copies lors de son appel. Il fournit également une entrée au programme (ici (:*:*), c'est-à-dire 4) et imprime la sortie à l'aide deS .

Explication

La sous-charge est étonnamment adaptée à cette tâche comme le font les tarpits de Turing, ayant des primitives utiles telles que "copier" et "entourer de parenthèses". (D'une manière ou d'une autre, Underload, normalement un langage très verbeux, bat Mathematica, normalement un langage qui gagne en raison d'un énorme ensemble de commandes internes, via des commandes internes plus appropriées!) Voici comment fonctionne le programme:

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

L'exponentiation de la fonction fait que les étapes de la fonction se répètent autant de fois, par exemple, (:a*)³ le serait (:a*:a*:a*). C'est la façon idiomatique d'écrire une boucle qui se répète un nombre donné de fois dans Underload. (Vous pouvez noter que le ~^est décrit de deux manières différentes ci-dessus; c'est parce que les entiers dans Underload sont définis comme une exponentiation de fonction spécialisée pour cet entier, donc pour faire une exponentiation de fonction, vous essayez simplement d'exécuter un entier comme s'il s'agissait d'une fonction .)

ais523
la source
2

APL (NARS), 15 caractères, 30 octets

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

tester:

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

Je ne sais pas si cela serait accepté ... Zilde est ⍬ ici, il représente l'ensemble de vides {} si je veux imprimer l'élément Zilde ou un élément plein de Zilde, et Zilde enfermé tout ce qui se passe n'est rien imprimer ... donc pour voir Zilde, il faut définir une fonction que j'appelle o (o←⎕fmt ) je pas dans le compte car l'élément et sa structure existent même si le sys ne l'imprime pas ... C'est possible si io vaut 0

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

pourrait aussi être une solution à 12 caractères ...

RosLuP
la source
1

Brachylog , 14 octets

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

Essayez-le en ligne!

Explication

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

GAP , 22 octets

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

Par exemple:

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

Raquette 119 octets

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

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

Test (In Racket {} est identique à () et la sortie par défaut est ()):

(f 4)

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

Pour voir clairement chaque numéro (0 à 3):

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

'()
'(())
'(() (()))
'(() (()) ((()) ()))
rnso
la source
1

Lot, 74 octets

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

Utilise le fait que chaque réponse est égale à la réponse précédente insérée en elle-même après l'interlignage {. Les premières sorties sont les suivantes:

{}

{{}}

{{{}}{}}

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

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

{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}
Neil
la source
Pouvez-vous publier un exemple montrant les formats d'entrée et de sortie?
Luis Mendo