Satu set n
angka positif memiliki 2^n
himpunan bagian. Kami akan memanggil set "bagus" jika tidak ada himpunan bagian dari jumlah yang sama. {2, 4, 5, 8}
adalah satu set yang bagus. Karena tidak ada himpunan bagian dari jumlah yang sama, kami dapat mengurutkan himpunan bagian dengan jumlah:
[{}, {2}, {4}, {5}, {2, 4}, {2, 5}, {8}, {4, 5}, {2, 8}, {2, 4, 5}, {4, 8}, {5, 8}, {2, 4, 8}, {2, 5, 8}, {4, 5, 8}, {2, 4, 5, 8}]
Jika kita memberi label angka [2, 4, 5, 8]
dengan simbol [a, b, c, d]
dalam urutan yang meningkat, kita mendapatkan urutan abstrak berikut:
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]
Satu set angka positif yang bagus dapat memiliki urutan abstrak yang sama, atau yang berbeda. Misalnya, [3, 4, 8, 10]
adalah set yang bagus dengan urutan abstrak yang berbeda:
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]
Dalam tantangan ini, Anda harus menghitung jumlah urutan abstrak yang berbeda dari set n
angka positif yang bagus. Urutan ini adalah OEIS A009997 , dan nilai yang diketahui, mulai dari n=1
, adalah:
1, 1, 2, 14, 516, 124187, 214580603
Misalnya, untuk n=3
, berikut ini adalah dua urutan abstrak yang mungkin:
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}]
Sebab n=4
, berikut ini adalah 14 pemesanan abstrak yang mungkin, ditambah contoh yang bagus dengan pemesanan itu:
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 2, 1]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 6, 3, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 4, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 1]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 4, 3]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 7, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 5, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 6, 2]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 3]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 6, 3]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 5, 4]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [7, 6, 5, 3]
Berikut ini bukan pemesanan abstrak yang valid:
{}, {a}, {b}, {c}, {d}, {a,b}, {e}, {a,c}, {b,c}, {a,d}, {a,e}, {b,d}, {b,e}, {c,d}, {a,b,c}, {a,b,d}, {c,e}, {d,e}, {a,b,e}, {a,c,d}, {a,c,e}, {b,c,d}, {b,c,e}, {a,d,e}, {b,d,e}, {a,b,c,d}, {c,d,e}, {a,b,c,e}, {a,b,d,e}, {a,c,d,e}, {b,c,d,e}, {a,b,c,d,e}
Pemesanan ini menyiratkan bahwa:
d < a + b
b + c < a + d
a + e < b + d
a + b + d < c + e
Menyimpulkan ketidaksetaraan ini memberi:
2a + 2b + c + 2d + e < 2a + 2b + c + 2d + e
yang merupakan kontradiksi. Kode Anda tidak boleh menghitung pemesanan ini. Contoh tandingan semacam itu pertama kali muncul di n=5
. Contoh dari makalah ini , contoh 2.5 di halaman 3.
Pemesanan ini tidak valid terlepas dari kenyataan yang A < B
menyiratkan bahwa A U C < B U C
, untuk setiap C
pemisahan dari A
dan B
.
Kode atau program Anda harus cukup cepat sehingga Anda dapat menjalankannya sampai selesai n=4
sebelum mengirimkannya.
Pengajuan dapat berupa program, fungsi, dll. Seperti biasa.
Celah standar dilarang, seperti biasa. Ini kode golf, jadi jawaban tersingkat dalam byte menang. Jangan ragu untuk mengajukan pertanyaan klarifikasi dalam komentar.
sumber
Jawaban:
Python 3 + SciPy,
396390385351336355 byteCobalah online!
Ini sekarang berjalan selama n = 5 dalam waktu sekitar 5 detik. The
if~-(v in u):
dapat dihapus karena -18 byte tetapi hukuman kinerja besar.Jika Anda ingin mencetak semua urutan abstrak seperti yang ditemukan alih-alih hanya menghitungnya, tambahkan
if c:print(s.x.round(),y)
sebelumfor
loop. (Himpunan bagian diwakili oleh bilangan bulat biner di mana setiap bit sesuai dengan ada atau tidak adanya satu elemen: { a , c , d } ↔ 1101₂ = 13.)Bagaimana itu bekerja
f
secara rekursif menghitung urutan abstrak memenuhi daftar kendala yang diberikan. Kita mulai dengan batasan n ≤ a , a + n ≤ b , b + n ≤ c , c + n ≤ d . Menggunakan pemrograman linier, kami menemukan solusi untuk kendala (atau mengembalikan 0 jika tidak ada) —dalam kasus ini, kami mendapatkan a = 4, b = 8, c = 12, d = 16. Kami mencari solusi untuk bilangan bulat , lalu hitung pemesanan referensi dengan mengurutkan semua himpunan bagiannya dengan jumlah mereka:{ a }, { b }, { c }, { a , b }, { d }, { a , c }, { a , d }, { b , c }, { b , d }, { a , b , c }, { c , d }, { a , b , d }, { a , c , d }, { b , c , d }, {a , b , c , d }
Pembulatan tidak dapat menyebabkan kendala dilanggar oleh lebih dari n / 2, itulah sebabnya kami menambahkan margin n .
Karena Python
sorted
stabil, ikatan apa pun antara himpunan bagian diputus dalam urutan leksikografis terbalik yang sama dengan yang kami hasilkan. Jadi kita bisa membayangkan mengganti { a , b , c , d } dengan { a · 2 ^ n + 2 ^ 0, b · 2 ^ n + 2 ^ 1, c · 2 ^ n + 2 ^ 2, d · 2 ^ n + 2 ^ 3} untuk mendapatkan pemesanan yang sama tanpa ikatan apa pun.Rencananya adalah untuk mengkategorikan semua pemesanan abstrak lainnya dengan analisis kasus berdasarkan di mana mereka pertama kali tidak setuju dengan pemesanan referensi:
{ A }> { b },
atau { a } <{ b }> { c },
atau { a } <{ b } <{ c }> { a , b },
atau { a } <{ b } < { c } <{ a , b }> { d },
⋮
Dalam setiap kasus, kami menambahkan kendala baru ini dengan margin n , dan memanggil secara rekursif
f
dengan kendala baru yang ditambahkan.Catatan
Untuk sementara saya menduga (tetapi tidak berasumsi) bahwa solusi program linear dengan margin 1 pada kendala akan selalu berupa bilangan bulat. Ini ternyata salah: contoh tandingan dengan n = 7 adalah {2.5, 30, 62.5, 73.5, 82, 87.5, 99.5}.
Python, 606 byte (lebih cepat, tidak ada perpustakaan eksternal)
Cobalah online!
Ini berjalan selama n = 5 dalam seperempat detik, dan n = 6 dalam 230 detik (75 detik dalam PyPy).
Ini termasuk pemecah pemrograman linier kode tangan menggunakan matematika integer dalam koordinat homogen untuk menghindari masalah pembulatan titik mengambang.
sumber
options={'tol':.1}
, yang tampaknya mengatasi masalah.Ruby, 308 byte, jauh lebih cepat
Menjalankan case 4 dalam ~ 150ms. Tidak ada perpustakaan khusus yang digunakan.
Sebagai contoh, ini secara rekursif menyelingi hasil dari kasus kecil
dengan himpunan bagian yang sesuai dengan elemen tambahan ditambahkan - mereka harus menjaga urutan relatif yang sama. Ini juga memastikan bahwa singleton baru ditambahkan setelah semua lajang sebelumnya.
Bagian yang memeriksa kepatuhan sama dengan sebelumnya, tetapi bukan kombinasi untuk menguji yang jauh lebih sedikit.
Versi yang diperluas dan dikomentari:
Ruby, 151 byte, cukup lambat
(case dari tiga elemen membutuhkan << 1s, case dari empat masih berjalan)
Ini berfungsi pada representasi bitfield dari subset, jadi orang mungkin harus memijat output jika diperlukan untuk menampilkan subset itu sendiri.
diformat:
sumber
...x-1
=>..x-2
,.select{...}.count
=>.count{...}
,|(x,y)|
=>|x,y|
,x&~y==0||y&~x!=0
=>x&~y<1||y&~x>0
karenaa&~b
tidak boleh negatif jika saya tidak salahn=5
contoh balasan yang baru saja saya tambahkan. Jika saya tidak salah, kode Anda akan menerimanya.P
, sehingga tidak bisa anonim. Juga, saya pikir itu masih gagal karena contoh tandingan yang saya posting.P=
). Juga, saya pikir Anda harus mengembalikan nomor sehingga Anda mungkin harus memasukkan.size
di sana di suatu tempat.