Pertama, beberapa definisi:
- Diberikan
n
dank
, pertimbangkan daftar multiset yang diurutkan , di mana untuk setiap multiset kami memilihk
angka{0, 1, ..., n-1}
dengan pengulangan.
Misalnya, untuk n=5
dan k=3
, kami memiliki:
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), (0, 1, 1), ( 0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 2), (0, 2, 3), (0, 2, 4), (0, 3, 3), (0, 3, 4), (0, 4, 4), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 3), (1, 3, 4), (1, 4, 4) , (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 3, 4), (2, 4, 4), ( 3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)]
- Sebuah bagian adalah daftar multisets dengan properti yang ukuran persimpangan semua multisets di bagian setidaknya
k-1
. Yaitu kita mengambil semua multiset dan memotongnya (menggunakan persimpangan multiset) sekaligus. Sebagai contoh,[(1, 2, 2), (1, 2, 3), (1, 2, 4)]
adalah bagian karena persimpangannya berukuran 2, tetapi[(1, 1, 3),(1, 2, 3),(1, 2, 4)]
tidak, karena persimpangannya berukuran 1.
Tugas
Kode Anda harus mengambil dua argumen n
dan k
. Maka harus dengan rakus pergi melalui multisets ini dalam urutan dan output bagian daftar. Untuk kasus ini n=5, k=3
, partisi yang benar adalah:
(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4)
(0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4)
(0, 2, 2), (0, 2, 3), (0, 2, 4)
(0, 3, 3), (0, 3, 4)
(0, 4, 4)
(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4)
(1, 2, 2), (1, 2, 3), (1, 2, 4)
(1, 3, 3), (1, 3, 4)
(1, 4, 4)
(2, 2, 2), (2, 2, 3), (2, 2, 4)
(2, 3, 3), (2, 3, 4)
(2, 4, 4)
(3, 3, 3), (3, 3, 4)
(3, 4, 4), (4, 4, 4)
Berikut adalah contoh lain untuk n = 4, k = 4
.
(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3)
(0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3)
(0, 0, 2, 2), (0, 0, 2, 3)
(0, 0, 3, 3)
(0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3)
(0, 1, 2, 2), (0, 1, 2, 3)
(0, 1, 3, 3)
(0, 2, 2, 2), (0, 2, 2, 3)
(0, 2, 3, 3), (0, 3, 3, 3)
(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3)
(1, 1, 2, 2), (1, 1, 2, 3)
(1, 1, 3, 3)
(1, 2, 2, 2), (1, 2, 2, 3)
(1, 2, 3, 3), (1, 3, 3, 3)
(2, 2, 2, 2), (2, 2, 2, 3)
(2, 2, 3, 3), (2, 3, 3, 3)
(3, 3, 3, 3)
Klarifikasi tentang apa yang serakah artinya: Untuk setiap multiset pada gilirannya kita melihat apakah itu dapat ditambahkan ke bagian yang ada. Kalau bisa kita tambahkan saja. Jika tidak bisa kita mulai bagian baru. Kami melihat multiset dalam urutan seperti pada contoh di atas.
Keluaran
Anda dapat menampilkan partisi dalam format apa pun yang Anda suka. Namun, multiset harus ditulis secara horizontal pada satu baris. Itu adalah multiset individu tidak boleh ditulis secara vertikal atau tersebar di beberapa baris. Anda dapat memilih bagaimana Anda memisahkan representasi bagian-bagian dalam output.
Asumsi
Kita bisa berasumsi itu n >= k > 0
.
sumber
(0, 4, 4)
dengan sendirinya? Dengan uraian Anda, saya akan berpikir "bagian" akan menjadi(0, 4, 4), (1, 4, 4), (2, 4, 4), (3, 4, 4), (4, 4, 4)
. Demikian pula untuk(0, 0, 3, 3)
pada test case kedua.Jawaban:
Jelly ,
2625 byteProgram lengkap yang mencetak representasi dari daftar daftar, setiap daftar menjadi bagian, misalnya untuk n = 5, k = 3:
Catatan: representasi yang digunakan menghilangkan daftar panjang 1
[
dan sekitar redundan]
.Cobalah online! atau lihat versi cetak yang cantik (biaya 3 byte)
Bagaimana?
sumber
MATLAB, 272 byte
Keluaran:
Dua garis kosong antara bagian yang berbeda.
Tidak Disatukan:
Penjelasan:
Pertama kita menemukan semua multiset dengan kekuatan kasar:
repmat(0:n-1, 1, k)
mengulangi vektor nilai dari waktu0
ken-1
k
waktu.nchoosek(x, k)
mengembalikan sebuah matriks yang berisi semua kombinasi k dari vektor yang diulang.sort(x, 2)
mengurutkan semua kombinasi-k, dan kemudianunique(x, 'rows')
menghapus semua duplikat.p=zeros(0,k);
membuat matriks kosong dengank
kolom. Kami akan menggunakannya sebagai tumpukan. Pada setiap iterasi dari outernmostfor
lingkaran, pertama kita tambahkan multiset saat ini untuk mengatakan stack:p=[p;l(i,:)];
.Kemudian kami memeriksa apakah persimpangan semua multiset dalam tumpukan setidaknya
k-1
panjang dengan kode berikut (kami tidak dapat menggunakanintersect
perintah MATLAB untuk memeriksa persimpangan, karena mengembalikan set, tetapi kami membutuhkan multiset):Sekarang, jika persimpangan cukup panjang
a == 0
,, sebaliknyaa == 1
.Jika persimpangan tidak cukup panjang, kami mencetak baris baru dan mengosongkan tumpukan:
Kemudian kita cukup mencetak multiset saat ini:
sumber
MATL , 34 byte
Bagian-bagian dipisahkan oleh garis yang berisi spasi putih.
Cobalah online!
Penjelasan
Penafian: metode ini tampaknya berhasil (dan memang ada dalam kasus uji), tapi saya tidak punya bukti bahwa itu selalu berhasil
Multiset diurutkan, baik secara internal (yaitu masing-masing multiset memiliki entri yang tidak berkurang) dan secara eksternal (yaitu multiset M datang sebelum multiset N jika M mendahului N secara leksikografis).
Untuk menghitung persimpangan multiset, multiset yang diurutkan disusun sebagai baris matriks dan perbedaan berturut-turut dihitung di sepanjang setiap kolom. Jika semua kolom kecuali paling banyak satu memiliki semua perbedaan sama dengan nol, multiset milik bagian yang sama.
Tes ini akan memberikan hasil negatif palsu untuk multiset seperti
(1,2,3)
dan(2,3,4)
: bahkan jika2
,3
entri umum, mereka tidak akan terdeteksi karena mereka berada di kolom yang tidak cocok.Namun, ini tampaknya tidak menjadi masalah, setidaknya dalam kasus uji. Tampaknya tes antara multiset suka
1,2,3
dan2,3,4
tidak pernah benar-benar harus dilakukan, karena beberapa multiset menengah memberikan hasil negatif sehingga mereka sudah berada di bagian yang berbeda. Jika ini memang benar, alasannya pasti ada hubungannya dengan fakta bahwa multisets diurutkan.Saya tidak punya bukti tentang ini. Sepertinya berfungsi.
sumber
n=k=4
kasus kita memiliki bagian baru mulai(0, 0, 3, 3)
, perbedaan berturut-turut yang di -vektor-kan dari itu dan multi-set sebelumnya,(0, 0, 2, 3)
hanya memiliki satu perbedaan, jadi bagaimana "bagian sejauh ini" membuat pekerjaan ini? (atau setara dengan apa hasil langkah sebelumnya yang digunakan alih-alih(0, 0, 2, 3)
?)PHP, 245 Bytes
Cobalah online!
Diperluas
Output sebagai String
n> 15 untuk lebih presisi
sumber
0
untuk(16**16-1)%16
dan pekerjaan versi panjang hanya dengan presisi yang diperlukan untukn>15
bcmod(bcsub(bcpow(16,16),1),16)
adalah15
php.net/manual/en/ref.bc.php