Konstruksi alami

27

Bilangan asli termasuk 0 secara resmi didefinisikan sebagai set, dengan cara berikut :

  • Angka 0 didefinisikan sebagai set kosong, {}
  • Untuk n ≥ 0, angka n +1 didefinisikan sebagai n ∪ { n }.

Akibatnya, n = {0, 1, ..., n -1}.

Angka pertama, yang ditentukan oleh prosedur ini, adalah:

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

Tantangan

Mengingat n, output perwakilannya sebagai satu set.

Aturan

Output secara konsisten dapat menggunakan braket karakter seperti {}, [], ()atau <>. Karakter sewenang-wenang (seperti 01) tidak diperbolehkan.

Alih-alih koma seperti di atas, pemisah dapat berupa tanda baca apa pun; atau mungkin tidak ada.

Spasi (bukan baris baru) dapat dimasukkan secara sewenang-wenang dan tidak konsisten.

Misalnya, angka 2 dengan tanda kurung dan titik koma sebagai pemisah [[]; [[]]], atau setara [ [ ]; [ [ ] ] ], atau genap[ [ ] ;[ []]]

The rangka di mana unsur-unsur dari suatu himpunan yang ditentukan tidak masalah. Jadi, Anda dapat menggunakan urutan apa pun dalam representasi. Misalnya, ini adalah beberapa output yang valid untuk 3:

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

Anda dapat menulis suatu program atau fungsi . Output mungkin berupa string atau, jika menggunakan fungsi, Anda dapat mengembalikan daftar atau array bersarang yang representasi stringnya sesuai dengan yang di atas.

Uji kasus

0  ->  {}
1  ->  {{}}
2  ->  {{},{{}}}
3  ->  {{},{{}},{{},{{}}}}
4  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
5  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}
6  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}}
7  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}}}
Luis Mendo
sumber
Terkait
Luis Mendo

Jawaban:

8

Jelly , 3 byte

Ḷ߀

Ini adalah tautan monadik. Cobalah online!

Bagaimana itu bekerja

Setiap bilangan asli adalah himpunan semua bilangan asli sebelumnya, yaitu, n = {0, ..., n-1} . Karena tidak ada bilangan asli yang mendahului 0 , kita memiliki 0 = {} .

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

Ḷ    Unlength; yield [0, ..., n-1].
 ߀  Recursively map this link over the range.
Dennis
sumber
3
"Unlength" Saya suka fungsi terbalik Jelly.
ETHproduksi
1
Jika saya mengerti dengan benar, pada dasarnya kisaran adalah [0, n)?
Downgoat
5
@Downgoat Itu benar. Saya mencoba untuk menjaga huruf dan huruf dengan titik di bawah sebagai terbalik lateral. Karena ḶLadalah no-op, mnemonik tidak memiliki panjang. Ada juga yang tidak biner, undecimal, unhalve, unsine, unarccosine, dll.
Dennis
1
Tunggu, tidak dituliskan? Bukankah itu hanya cosinus?
ETHproduk
@ EHProduk Yup. Tidak ada C dengan titik di bawah ini.
Dennis
18

Python 2, 26 byte

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

Uji di Ideone .

Dennis
sumber
10

JavaScript (ES6), 32 byte

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

Cukup sederhana.

Produksi ETH
sumber
1
@Downgoat Saya pikir ini mungkin pertama kalinya saya menggunakan .map()tanpa fungsi panah di dalam :-)
ETHproductions
baik secara teknis f adalah fungsi panah: P
Downgoat
@ EHProduk Sungguh? .map(Number)adalah kasus yang cukup umum.
Sebastian Simon
@Xufox Poin bagus, saya pikir saya sudah melakukannya setidaknya sekali.
ETHproduk
4
@Xufox Meskipun .map(e=>+e)lebih pendek, dengan satu byte.
Conor O'Brien
7

Perl 6 , 16 byte

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

Mengembalikan struktur data bersarang.

Contoh:

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

Penjelasan:

{   # 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
sumber
Ini ... mengesankan.
Conor O'Brien
6

Ruby, 27 21 byte

Saya baru mengenal golf ruby, tapi tidak ada yang terjadi. Terima kasih kepada Jordan karena telah menghemat 6 byte!

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

Ini adalah fungsi rekursif f(proc, untuk lebih spesifik) dan mengambil argumen s. Ini memetakan proc di fatas 0...s, yang merupakan kisaran [0, s).

Conor O'Brien
sumber
Anda bisa menggantinya map{|e|f[e]}dengan map &f.
Jordan
@ Jordan Wow, bagus!
Conor O'Brien
5

Haskell, 32 27 byte

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

Cobalah di Ideone.

Laikoni
sumber
4

CJam , 14 byte

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

Cobalah online!

Penjelasan

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

Dalam setiap iterasi, blok membangun representasi dari angka dari yang sebelumnya. Untuk mengilustrasikannya, mari kita perhatikan iterasi kedua, di mana representasi angka 2dibangun dari 1, yaitu string "[[]]".

  1. Tumpukan berisi "[[]]"
  2. Setelah pernyataan _(duplikat) itu berisi "[[]]","[[]]"
  3. Setelah pernyataan )(uncons) mengandung "[[]]", "[[]","]"
  4. Setelah pernyataan @(rotate) mengandung "[[]", "]","[[]]"
  5. Setelah pernyataan \(swap) mengandung "[[]", "[[]]","]"
  6. Setelah pernyataan ](masukkan ke dalam array) yang dikandungnya ["[[]" "[[]]" "]"], yang akan ditampilkan sebagai string "[[][[]]]".
Luis Mendo
sumber
4

Cheddar, 17 byte

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

Rekursi pendek + Jarak pendek + Iterasi pendek = Tantangan di mana cheddar bekerja dengan sangat baik

Non-bersaing, 11 byte

n f->|>n=>f

The =>Operator ditambahkan setelah tantangan ini dirilis membuat jawaban ini non-bersaing.

Ini mungkin terlihat membingungkan tetapi izinkan saya menyederhanakannya:

n f -> |> n => f

pada dasarnya nadalah input dan ffungsi itu sendiri. |>nmenghasilkan [0, n) dan =>peta yang berakhir f.

Downgoat
sumber
1
Yang tidak bersaing terlihat sangat bagus: D
Conor O'Brien
4

05AB1E , 8 7 byte

)IF)©`®

Penjelasan

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

Cobalah online!

Disimpan 1 byte berkat Adnan.

Emigna
sumber
Kurang dari 2 menit LOL
Luis Mendo
@LuisMendo Saya benar-benar baru saja masuk ketika tantangan itu diposting :)
Emigna
Saya percaya Anda dapat menghapus braket terakhir: p
Adnan
@ Adnan: Ups. Saya tidak tahu bagaimana saya melewatkan hal itu :)
Emigna
3

Pyth, 4 byte

LyMb

Suite uji

L: Tentukan fungsi ydengan inputb

yMb: ydipetakan pada rentang0, 1, ..., b-1

Pada input 0, peta ini kembali []. Jika tidak, ia kembali ydipetakan di atas semua nomor hingga b.

isaacg
sumber
3

MATL , 13 byte

Xhi:"tY:Xh]&D

Cobalah online!

Penjelasan

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
sumber
2
Jawaban yang sangat cerdas
Suever
@Suever Terima kasih! Terlalu lama ...
Luis Mendo
3

Perl, 27 byte

Termasuk +1 untuk -p

Banyak metode berbeda yang semuanya berakhir sebagai 27 atau 28 byte. misalnya

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

Yang terbaik yang bisa saya temukan adalah

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

karena pada perl yang lebih lama Anda dapat menjatuhkan spasi sebelum fordan mendapatkan 26 byte

Ton Hospel
sumber
3

Mathematica, 14 byte

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

Mathematica, 31 byte

Menerapkan definisi sebagai daftar bersarang. Menggunakan fungsi tanpa nama yang secara rekursif menyebut dirinya menggunakan #0.

If[#<1,{},Join[t=#0[#-1],{t}]]&
Greg Martin
sumber
4
Anda dapat menghemat banyak dengan menggunakan operator bernama dan Unionbukannya Join: ±0={};±n_:={t=±(n-1)}⋃t... Namun, dalam hal ini bahkan lebih pendek untuk solusi berulang:Nest[{#}⋃#&,{},#]&
Martin Ender
2

Retina , 24 18 byte

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

Cobalah online! (Baris pertama memungkinkan suite tes yang dipisahkan dengan linefeed.)

Penjelasan

.+
$*1<>

Ini mengubah input ke unary dan menambahkan <>, representasi dari 0.

+`1<
<<$'

Di sini, ini +menunjukkan bahwa substitusi ini harus dijalankan dalam satu lingkaran sampai string berhenti berubah. Lebih mudah untuk menjelaskan hal ini dengan melalui langkah-langkah individual yang saya lakukan saat bermain golf. Mari kita dengan versi substitusi ini:

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

Ini cocok dengan yang terakhir 1dari representasi unary dari input yang tersisa (untuk menghapusnya dan mengurangi input), serta isi dari set saat ini di bagian akhir. Ini kemudian diganti dengan set baru yang berisi yang sebelumnya serta isinya. Namun, kita dapat melihat bahwa $1diikuti oleh >dalam kedua kasus dan karenanya kita dapat memasukkannya dalam tangkapan itu sendiri dan menghilangkannya dari pola substitusi. Itu mengarah ke formulir

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

Namun, sekarang kita dapat mengamati bahwa (.*)hanya menangkap akhiran string setelahnya 1<dan kita bahkan memasukkan akhiran ini di akhir $1. Karena sintaksis substitusi memberi kita cara untuk merujuk ke bagian string setelah kecocokan dengan $'kita bisa dengan mudah menghilangkan kedua bagian itu dan berakhir dengan versi yang digunakan dalam jawaban:

1<
<<$'
Martin Ender
sumber
Anda yakin ini adalah Retina dan bukan bahasa> <>? :-P
Luis Mendo
@LuisMendo Saya kira saya bisa menggunakan {}, tetapi <>satu-satunya pasangan yang tidak perlu melarikan diri, jadi saya pikir saya akan pergi dengan itu. ;)
Martin Ender
2

Underload , 14 byte

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

Cobalah online!

Program penuh underload tidak dapat mengambil input melalui salah satu metode yang kami tentukan, jadi ini adalah fungsi yang mengambil input dari stack sebagai angka Gereja (cara normal untuk mendefinisikan bilangan bulat di Underload), dan menghasilkan output ke stack sebagai string .

Para (…)penanda pengelompokan yang diperlukan untuk membuat fungsi ini (dapat digunakan kembali) daripada potongan (hanya dapat digunakan sekali). Pembungkus dalam tautan TIO menyebut fungsi yang dimaksud menggunakan destruktif ^, tetapi bisa digunakan kembali dengan membuat salinannya dan hanya mengonsumsi salah satu salinan saat memanggilnya. Ini juga memberikan input ke program (di sini (:*:*),, yaitu 4), dan mencetak output menggunakan S.

Penjelasan

Underload secara mengejutkan cocok untuk tugas ini ketika Turing pergi, memiliki primitif yang bermanfaat seperti "copy" dan "surround dengan tanda kurung". (Entah bagaimana, Underload, biasanya bahasa yang sangat bertele-tele, mengalahkan Mathematica, biasanya bahasa yang menang karena memiliki satu set besar builtin, melalui memiliki lebih banyak builtin yang sesuai!) Inilah cara kerja program:

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

Eksponensiasi fungsi secara efektif menyebabkan langkah-langkah fungsi berulang yang berkali-kali, jadi, misalnya. (:a*)Akan menjadi (:a*:a*:a*). Itulah cara idiomatis untuk menulis sebuah loop yang mengulang beberapa kali dalam Underload. (Anda dapat mencatat bahwa ~^dijelaskan dua cara berbeda di atas; itu karena bilangan bulat dalam Underload didefinisikan sebagai fungsi eksponensial yang dikhususkan untuk integer itu, jadi untuk melakukan fungsi eksponensial, Anda cukup mencoba menjalankan integer seolah-olah itu adalah fungsi. .)

ais523
sumber
2

APL (NARS), 15 karakter, 30 byte

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

uji:

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

Saya tidak tahu apakah ini akan diterima ... Zilde adalah ⍬ di sini ia mewakili set kosong {} jika saya ingin mencetak elemen Zilde atau satu elemen penuh Zilde, dan Zilde menyertakan semua yang terjadi adalah mencetak apa-apa ... jadi untuk melihat Zilde kita harus mendefinisikan satu fungsi yang saya sebut o ( o←⎕fmt) Saya tidak memasukkan dalam hitungan karena elemen dan strukturnya ada bahkan jika sys tidak mencetaknya ... Mungkin jika io adalah 0

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

bisa menjadi solusi 12 karakter juga ...

RosLuP
sumber
1

Brachylog , 14 byte

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

Cobalah online!

Penjelasan

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

GAP , 22 byte

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

Sebagai contoh:

gap> f(3);                            
[ [  ], [ [  ] ], [ [  ], [ [  ] ] ] ]
Sievers Kristen
sumber
1

Racket 119 byte

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

Tidak Disatukan:

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

Pengujian (In Racket {} sama dengan () dan output default adalah ()):

(f 4)

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

Untuk melihat dengan jelas setiap angka (0 hingga 3):

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

'()
'(())
'(() (()))
'(() (()) ((()) ()))
juga
sumber
1

Batch, 74 byte

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

Menggunakan fakta bahwa setiap jawaban sama dengan jawaban sebelumnya yang dimasukkan ke dalam dirinya sendiri setelah memimpin {. Beberapa output pertama adalah sebagai berikut:

{}

{{}}

{{{}}{}}

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

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

{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}
Neil
sumber
Bisakah Anda memposting contoh yang menunjukkan format input dan output?
Luis Mendo