Tantangannya adalah untuk membuat daftar semua partisi yang dipesan (komposisi (kombinatorik)) dari bilangan bulat positif yang diberikan n
. Ini adalah daftar nomor dari 1
ke n
yang jumlahnya adalah n
. Misalnya, diberi masukan n = 4
, hasilnya harus:
4
1, 3
3, 1
2, 2
2, 1, 1
1, 2, 1
1, 1, 2
1, 1, 1, 1
Hasilnya bisa dalam urutan apa pun, tetapi harus berisi setiap partisi yang dipesan satu kali. Ini berarti bahwa untuk n = 4
, [1, 1, 2]
, [1, 2, 1]
dan [2, 1, 1]
semua harus menjadi bagian dari hasilnya.
Ini kode JavaScript saya sendiri yang mencapai ini:
function range(n) {
for (var range = [], i = 0; i < n; range.push(++i));
return range;
}
function composition(n) {
return n < 1 ? [[]] : range(n).map(function(i) {
return composition(n - i).map(function(j) {
return [i].concat(j);
});
}).reduce(function(a, b) {
return a.concat(b);
});
}
Golfed, ES6 ( 169 167 119 109 105 89 85 bytes ):
n=>n?[].concat(...[...Array(n)].map((x,i)=>i+1).map(b=>m(n-b).map(a=>[b,...a]))):[[]]
Jawaban:
Pyth,
76 byteSolusi 7 byte:
Pyth memiliki built-in partisi integer
./
, jadi 5 dari 7 byte mendapatkan urutan.Cobalah online!
Penjelasan:
Solusi 6 byte:
Jika Anda memiliki daftar,
./
akan dihitung dengan pemesanan; yang tersisa hanyalah membuat daftar angka lagi.Cobalah online!
Penjelasan:
sumber
Haskell, 37 byte
xnatau menyimpan dua byte.
sumber
f n=[a:x|a<-[1..n],x<-f$n-a]
lebih pendek.given positive integer n ... numbers from 1 to n
)f 0=[[]]
kebetulan merupakan alas yang lebih pendek darif 1=[[1]]
:)Python, 56 byte
Solusi rekursif: Partisi yang diurutkan
n
adalah partisii
dengan yang lebih kecil0<=i<n
, diikuti oleh sisanyan-i
sebagai elemen terakhir. Untuk kasus dasar,n=0
hanya memiliki partisi kosong.sumber
Python 2, 61 byte
Ini bukan yang terpendek, tapi saya sangat suka metode ini karena sangat aneh.
Secara rekursif menghasilkan dan mengevaluasi
2**(n-1)
string, sepertiuntuk
n=4
. String ini mengevaluasi tupel yang mewakili semua partisi. Antara dua 1 adalah salah satu+
, bergabung dengan mereka menjadi satu nomor, atau a,
, membelah bagian yang berdekatan.sumber
import re
lambda n:map(lambda n:map(len,re.finall('10*',bin(n))),range(1<<n-1,1<<n))
JavaScript (Firefox 30-57), 63 byte
sumber
f=n=>n<2?[[1]]:f(n-1).map(([n,...a])=>r.push([1+n,...a],[1,n,...a]),r=[])&&r
.Mathematica, 40 byte
Built-in untuk partisi integer Mathematica tidak memberikan semua partisi yang dipesan , jadi kami harus membuat semua permutasi yang mungkin dari masing-masing partisi tersebut , dan kemudian meratakan hasilnya.
sumber
CJam ,
1714 byteCobalah online!
Penjelasan
Saya tahu saya mengatakan bahwa menggunakan produk Cartesian lebih lama, tetapi saya akhirnya menemukan cara untuk menggunakannya dengan lebih efisien. Saya pikir kedua pendekatan itu menarik dengan caranya sendiri, jadi saya menempatkannya di pos terpisah.
Ini masih didasarkan pada gagasan bahwa, kita dapat memilih
n
waktu antara menambahkan a1
ke partisi saat ini atau untuk menambah elemen terakhir dari partisi saat ini. Dalam solusi ini, kami melakukan ini dengan menghasilkan 2 n-1 program berbeda yang sesuai dengan pilihan yang berbeda ini.sumber
)
". Jadi saya menambahed
dan menguji. +1 untuk penyalahgunaan kesalahan kreatif.Jelly ,
76 byte-1 byte terima kasih kepada @Dennis (konversi dari unary
ḅ1
, bukan penjumlahan untuk masing-masingS€€
)TryItOnline
Bagaimana?
sumber
Pure Bash, 51
Ini adalah port jawaban brilian @ xnor , menggunakan beberapa level ekspansi bash untuk mencapai hasil yang diinginkan:
Ideone.
$a
berisi1
diikuti olehn-1
nol.${a//0/{+,']\ $[}1'}
menggantikan masing-masing0
di$a
dengan salinan string{+,']\ $[}1'
. Jadi n = 4 kita mendapatkan string1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1'
$[
dan postfixed dengan],
memberi$[1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1]
$[1+1+1+1], $[1+1+1] 1, $[1+1] $[1+1], $[1+1] 1 1,...
Hati-hati menggunakan tanda kutip, garis miring terbalik dan
eval
memastikan bahwa ekspansi terjadi dalam urutan yang benar.sumber
Ruby, 61 byte
ungolfed
pemakaian
sumber
x<<i
lebih pendek dari[i]+x
..flatten(1)
bukan.flatten 1
?Brachylog , 20 byte
Cobalah online!
Penjelasan
Ini adalah situasi di mana Anda akan berpikir bahasa deklaratif akan bekerja dengan baik, tetapi karena kelebihan beban
+
dan kesulitan dalam menulis predikat penjumlahan yang menyebarkan kendala dengan benar, mereka tidak melakukannya.sumber
L
menjadi antara 1 dan masukan.+
juga bekerja pada bilangan bulat tunggal, saya perlu memaksakan.
untuk menjadi daftar##
, dan karena+
juga bekerja pada daftar daftar, saya perlu memaksakan bahwa elemen-elemen.
adalah bilangan bulat dengan:#$a
.CJam , 19 byte
Cobalah online!
Penjelasan
CJam tidak memiliki kombinatorik yang berguna untuk partisi integer. Jadi kami akan melakukan ini secara manual. Untuk menemukan semua partisi memerintahkan bilangan bulat
n
, kita dapat melihat daftarn
yang dan mempertimbangkan segala cara yang mungkin untuk memasukkan pemisah. Kemudian kita akan menjumlahkan1
di setiap bagian. Contoh untukn = 3
:Saya mencoba menggunakan produk Cartesian untuk menghasilkan semua pemisah ini, tetapi itu berakhir pada 21 byte. Sebaliknya saya kembali ke teknik lama ini untuk menghasilkan set daya (ini didasarkan pada jawaban tua Dennis tapi saya tidak dapat menemukannya sekarang). Idenya adalah ini: untuk menghasilkan semua partisi kita bisa mulai dari daftar kosong. Maka
n
kali kita dapat membuat keputusan biner: kita menambahkan a1
(sesuai dengan pemisah pada contoh di atas) atau kita menambah nilai terakhir dari daftar (sesuai dengan tidak memiliki pemisah). Untuk menghasilkan semua partisi, kami cukup melakukan kedua operasi di setiap langkah dan menjaga semua output yang mungkin untuk langkah berikutnya. Ternyata di CJam, menambahkan dan menambah elemen pertama lebih pendek, tetapi prinsipnya tetap sama:sumber
T-SQL, 203 byte
Golf:
Tidak Disatukan:
Biola
sumber
Mathematica 10.0, 44 byte
Upaya tanpa menggunakan bawaan yang terkait dengan partisi. Dari setiap partisi ukuran k yang diurutkan , dua partisi pengganti k + 1 dihasilkan: satu dengan menambahkan sebelumnya 1, dan yang lainnya dengan menambah nilai pertama.
Cara yang lebih lucu, tetapi sayangnya 2 byte lebih lama dalam mengimplementasikan ide yang sama:
sumber
MapAt
indeks ke -1.05AB1E ,
1412 byteDisimpan 2 byte berkat Adnan
Penjelasan
Cobalah online!
Solusi yang sesuai adalah 2 byte lebih pendek dalam 2sable .
2sable , 10 byte
Cobalah online!
sumber
—
bukannyaiy,
:).Haskell, 41 byte
Bukan solusi Haskell terpendek, tapi saya suka itu tidak menggunakan
[..]
rentang. Sebaliknya, ia secara rekursif menghitung partisin
sebagai partisin-1
dengan 1 baru di awal atau nilai pertama yang lebih tinggi. Ini menjelaskan mengapa ada2^(n-1)
dari mereka.sumber
Mathematica, 53 byte
Tidak mengalahkan jawaban Martin Ender, yang menggunakan
IntegerPartitions
fungsi bawaan (dan built-in benar-benar baik-baik saja bagi saya). (Juga tidak mengalahkan jawaban feersum, yang tidak saya lihat sampai terlambat.) Tetapi saya ingin mempraktikkan fungsi rekursif golf.Secara rekursif menghasilkan semua komposisi, dengan menghasilkan semua angka akhir yang mungkin
j
dan kemudian menyebut dirinya di#-j
mana#
input.sumber
Array
bukanTable
dan menghindariAppend
dengan menggunakan daftar danApply
:±0={{}};±n_:=Join@@Array[{##,n-+##}&@@@±#&,n,0]
@@
harus dilakukanf@@g[a,b]
evaluasi kef[a,b]
. Di sini kita menggunakan fakta bahwa daftar seperti{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }
kasat mata memiliki kepalaList
; jadiJoin@@{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }
mengevaluasi untukJoin@@List[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]
mengevaluasi untukJoin[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]
mengevaluasi{ {1,1,1}, {2,1}, {1,2}, {3} }
.Retina , 32 byte
Hitungan byte mengasumsikan penyandian ISO 8859-1.
Cobalah online!
Penjelasan
Ini bekerja mirip dengan jawaban CJam saya . Kami melewati daftar
N
yang dan pada setiap posisi kami mengambil kedua cabang dari keputusan biner a) menambah nilai terakhir atau b) memulai nilai baru pada 1.Tahap 1
Konversikan input ke unary.
Tahap 2
The
+
memberitahu Retina untuk melaksanakan tahap ini dalam satu lingkaran sampai output berhenti berubah. The%
mengatakan itu untuk membagi masukan ke garis sebelum menerapkan panggung dan bergabung dengan mereka kembali bersama-sama setelah itu. Dengan menempatkan%
setelah+
, Retina membelah dan bergabung kembali setelah setiap iterasi. Satu iterasi panggung membuat salah satu keputusan yang saya sebutkan dan dengan demikian membagi dua set partisi saat ini.Cara benar-benar bekerja adalah bahwa hal itu cocok dengan
1
(tapi hanya yang pertama yang ditunjukkan dengan1
di depan backtick), dan menggantinya dengan!
(yang akan kita gunakan sebagai digit unary output kami), diikuti oleh sisa1
s pada baris ini (ini menambah nilai terakhir). Kemudian pada baris lain (¶
) ia mencetak awalan dari baris saat ini, diikuti oleh,!
, yang menyisipkan pemisah dan kemudian mulai nilai berikutnya di1
.Tahap 3
Ini mengubah proses dari
!
ke bilangan bulat desimal dengan menggantinya dengan panjangnya.Tahap 4
Dan akhirnya, kami perhatikan bahwa kami telah menghasilkan dua kali lebih banyak garis yang kami inginkan, dan setengah dari mereka mulai dengan
,
(yang di mana kami awalnya membuat keputusan pemisahan, meskipun belum ada apa pun untuk dipisah setelah). Karenanya, kami membuang semua baris yang dimulai dengan a,
.sumber
Perl, 44 byte
Termasuk 3 untuk
-n
(menggunakan kode$'
dan$0
sehingga tidak dapat dijalankan sebagai-e
commandline)Berikan nomor pada partisi di STDIN:
partitions.pl
Jika Anda tidak keberatan dengan ruang ekstra di akhir baris dan baris baru ekstra, solusi 42 byte ini juga berfungsi (jalankan sebagai
perl -M5.010 partitions.pl
):sumber
Julia, 113 Bytes
Solusi non-rekursif
Dijelaskan:
[vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N]
buat serangkaian daftar yang menjumlahkan ke N, yang permutasi akan menyerupai solusi (misalnya untuk N = 4: [[1,1,1,1], [1,1,2], [1,3], [4 ]])map(x->[permutations(x)...],)
Hitung semua permutasireduce(vcat,)
menggabungkannya ke dalam daftar daftarunique()
filter duplikatsumber
N
sebagai masukan. Anda dapat membuat fungsi lambda denganN->
membebani dengan biaya 3 byte.f(N)=
hilang dalam menyalin, saya sudah memilikinya ketika menghitung byteMATL , 15 byte
Cobalah online!
Penjelasan
Masukan yang diberikan
n
, ini menghitung kekuatan Cartesian dengan eksponen yang meningkatk
dari1
ken
; dan untuk setiap eksponenk
memilih tupel yang memiliki jumlah yang sama dengan input.sumber
Lua
214203182 byteVersi tidak terpecahkan.
Menemukan spasi kosong dan menghapus variabel yang tidak perlu ke safe 11 byte. ternyata, table.insert () tidak efisien byte
sumber
PHP, 125 Bytes
-4 Bytes
print_r($r);
bukanecho json_encode($r);
untuk outputsolusi rekursif dengan 250 Bytes
sumber
Prolog, 81 byte + 6 byte untuk dipanggil
Cobalah online!
Hubungi dengan
[4]*L.
, ulangi dengan;
sampai semua solusi telah disajikan.Atau, jika berulang kali menekan
;
tidak oke (atau harus ditambahkan ke jumlah byte), panggil denganbagof(L,[4]*L,M).
yang menambahkan 17 byte untuk panggilan.sumber
J ,
3026 byteBekerja dengan memisahkan daftar unary n dengan menggunakan nilai biner 2 n .
Cobalah online!
Penjelasan
sumber
Sebenarnya,
1716 byteJawaban ini sebagian didasarkan pada jawaban MATL Luis Mendo . Saran bermain golf diterima. Cobalah online!
Tidak melakukanolf
sumber
Sebenarnya,
171615 byteIni adalah pertanda menarik dari jawaban CJam Martin Ender (yang dengan produk Cartesian), dengan perbedaan dalam implementasi yang saya pikir menarik. Ketika salah satu string Martin mulai dengan kenaikan, kesalahan mencegah string yang dievaluasi. Dalam Sebenarnya, kesalahan ditekan dan string tetap dievaluasi. Ini akhirnya memberikan komposisi setiap
k
dalam kisaran[1..n]
.Alih-alih mencoba untuk menghapus komposisi tambahan, saya mengambil
n-1
kekuatan Cartesian dari"1u"
ditambahkan"1"
ke awal setiap string. Trik ini hanya memberikan komposisin
. Sayangnya, ini lebih panjang dari jawaban Martin.Saran bermain golf diterima. Cobalah online!
Tidak melakukanolf
sumber