Aljabar Steenrod adalah aljabar penting yang muncul dalam topologi aljabar. Aljabar Steenrod dihasilkan oleh operator yang disebut "kotak Steenrod," yang ada untuk setiap bilangan bulat positif i. Ada dasar untuk aljabar Steenrod yang terdiri dari "monomial yang dapat diterima" dalam operasi kuadrat. Adalah tujuan kami untuk menghasilkan basis ini.
Urutan bilangan bulat positif disebut dapat diterima jika setiap bilangan bulat setidaknya dua kali lipat dari yang berikutnya. Jadi misalnya [7,2,1]
dapat diterima karena dan . Di sisi lain, tidak dapat diterima karena . (Dalam topologi kita akan menulis untuk urutannya ).[3,2]
[7,2,1]
The gelar berurutan adalah total dari entri itu. Jadi misalnya, derajatnya [7,2,1]
adalah . The kelebihan dari urutan diterima adalah elemen pertama dikurangi total dari unsur-unsur yang tersisa, sehingga memiliki kelebihan .[7,2,1]
Tugas
Tulislah sebuah program yang mengambil sepasang bilangan bulat positif (d,e)
dan mengeluarkan serangkaian semua deret derajat yang dapat diterima d
dan kelebihan kurang dari atau sama dengan e
. Outputnya adalah himpunan sehingga urutan urutan yang diterima tidak masalah.
Contoh:
Input: 3,1
Output: [[2,1]]
Di sini kami sedang mencari urutan diterima dengan total 3. Ada dua opsi, [3]
dan [2,1]
. ( [1,1,1]
dan [1,2]
memiliki jumlah 3 tetapi tidak dapat diterima). Kelebihannya [3]
adalah 3 dan selisihnya [2,1]
adalah . Dengan demikian, satu-satunya urutan dengan kelebihan adalah .[2,1]
Input: 6, 6
Output: [[6], [5, 1], [4, 2]] (or any reordering, e.g., [[5,1],[4,2],[6]])
Karena kelebihan selalu kurang dari atau sama dengan derajat, kami tidak memiliki kondisi berlebih. Jadi, kami hanya mencoba untuk menemukan semua urutan diterima dari tingkat 6. Pilihannya adalah [6]
, [5, 1]
, dan [4, 2]
. (Ini memiliki kelebihan , , dan 4 - 2 = 2. )
Input: 10, 5
Output: [[7,3], [7,2,1], [6,3,1]]
Urutan derajat 10 yang dapat diterima adalah:
[[10], [9,1], [8,2], [7,3], [7,2,1], [6,3,1]]
Ini memiliki kelebihan , , , , , dan masing-masing, jadi tiga yang terakhir semuanya bekerja.
Mencetak gol
Ini adalah kode golf: Solusi terpendek dalam byte yang menang.
Kasus uji:
Setiap pemesanan ulang output sama baiknya, jadi untuk input (3, 3)
, output [[3],[2,1]]
atau [[2,1],[3]]
sama-sama dapat diterima (namun [[1,2],[3]]
tidak).
Input: 1, 1
Output: [[1]]
Input: 3, 3
Output: [[2,1], [3]]
Input: 3, 1
Output: [[2,1]]
Input: 6, 6
Output: [[6], [5, 1], [4, 2]]
Input: 6, 4
Output: [[5,1], [4,2]]
Input: 6, 1
Output: []
Input: 7, 7
Output: [[7], [6,1], [4,2,1], [5,2]]
Input: 7,1
Output: [[4,2,1]]
Input: 10, 10
Output: [[10], [9,1], [7,2,1], [6,3,1], [8,2], [7,3]]
Input: 10, 5
Output: [[7,3], [7,2,1], [6,3,1]]
Input: 26, 4
Output: [15, 7, 3, 1]
Input: 26, 6
Output: [[16, 7, 2, 1], [16, 6, 3, 1], [15, 7, 3, 1], [16, 8, 2], [16, 7, 3]]
sumber
Jawaban:
05AB1E ,
1612 byteDisimpan 4 byte berkat Grimy
Cobalah online!
Penjelasan
sumber
ćsO-
adalah built-inÆ
.À@¨
bisa¦@
.Bahasa Wolfram (Mathematica) ,
6762 byteCobalah online!
-4 bytes oleh @attinat
IntegerPartitions@d
: Dapatkan semua daftar penjumlahan bilangan bulat ked
Cases[,...]
: Saring dengan ketentuan berikut:2#& @@# - d <= e &&
: Dua kali elemen pertama dikurangi jumlahnya kurang darie
, dan ...Max@Ratios@#<=.5
: Rasio elemen yang berurutan dari daftar semuanya kurang dari 1/2.Karena
e
kurang dari 0,5, kita bisa mengubahnya menjadi ketimpangan yang dirantai.Untuk beberapa byte tambahan, ini jauh lebih cepat: Coba online!
sumber
Jelly ,
1615 byte-1 berkat Erik the Outgolfer (penyesuaian cerdas untuk pemeriksaan yang memungkinkan filter tunggal)
Sebuah tautan diad yang menerima bilangan bulat positif
d
,, di sebelah kiri dan bilangan bulat positife
,, di sebelah kanan yang menghasilkan daftar daftar bilangan bulat positif.Cobalah online! (footer memformat hasil untuk menghindari daftar pemformatan daftar implisit yang dilakukan Jelly sebagai program lengkap)
Bagaimana?
sumber
Haskell ,
595854 byte1 byte disimpan berkat nimi
4 byte disimpan berkat xnor
Cobalah online!
sumber
#
secara langsung: Coba online!JavaScript (V8) ,
88 8781 byteMengambil input sebagai
(e)(d)
. Mencetak urutan ke STDOUT.Cobalah online!
Berkomentar
sumber
Pyth , 23 byte
Cobalah online!
sumber
Python 3 ,
213 bytePemahaman daftar raksasa. Kemungkinan besar bukan cara terbaik untuk melakukan ini, tapi saya tidak tahu bagaimana cara melewatkan pernyataan if
Python 3 , 172 byte
Cobalah online!
Sesuai dengan hasil edit oleh @Jonas Ausevicius
sumber
all
dapat mengambil generator sehingga Anda hanya dapat melakukanall(...)
bukanall([...])
. Terakhir karena kiriman Anda adalah fungsi yang sepenuhnya anonim, Anda tidak dikenakan sanksi atas penugasan (f=
) dan karenanya dapat menguranginya dari skor Anda (-2 byte).[*(...)]
bukannyalist(...)
yang biasanya menghemat satu byte tetapi dalam case Anda menghemat 2 karena juga memungkinkan Anda untuk menghapus spasi.[*filter(...)]
. Juga selamat datang :)Arang , 42 byte
Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:
Pertama buat daftar daftar dari
[1]..[d]
.Untuk setiap daftar, buat daftar baru dengan mengawali semua angka dari angka pertama yang digandakan hingga
d
dan menambahkan daftar itu ke daftar daftar yang akan diproses. Ini memastikan bahwa semua urutan yang diizinkan yang berisi angka tidak lebih besar darid
yang dibuat.Keluarkan hanya daftar yang derajat
d
dan kelebihannya tidak lebih besar darie
. (Jumlah derajat dan kelebihannya sama dengan dua kali angka pertama dari daftar.)sumber
Python 3 , 156 byte
mengambil
d,e
sebagai input; daftar keluaran tupelMirip dengan @OrangeCherries, jawab dan bantuan dari komentar; tetapi lebih banyak byte yang disimpan
Cobalah online!
sumber
Jelly , 18 byte
Cobalah online!
sumber
Ruby , 78 byte
Cobalah online!
sumber