Combinatorial Problem
kombinasi analisis kadang-kadang
mudah dengan formula standar yang tersedia. Misalnya, jumlah permutasi dari N
item hanya N! (N faktorial). Jika salah satu item (S) adalah sama, Anda hanya
membagi dengan S! untuk mendapatkan jawaban tanpa kesedihan. Demikian pula,
jumlah kombinasi (pilihan tanpa memperhatikan urutan) dari N item diambil R
pada suatu waktu mudah ditemukan dengan N! / R! (N-R) !.
Sayangnya, hal itu tidak lagi
menjadi mudah ketika Anda mempertimbangkan kombinasi mana beberapa item yang
sama, atau item partisi ke dalam kelompok. Rumus memang ada untuk banyak
situasi, tapi kadang-kadang mereka terlalu rumit untuk menjadi berguna. Dengan
kata lain, sering akan lebih cepat untuk memecahkan masalah secara langsung
oleh komputer daripada mencoba untuk mengatur dan memecahkan rumus. Setidaknya
itulah saya mengambil itu, memiliki pengetahuan yang baik dari matematika
praktis tetapi umumnya kehilangan di daerah seperti kalkulus.
Semua Spots
Dibuat Sama
Perhatikan masalah berikut:
Jika kartu spot (9-2) di masing-masing sesuai dianggap sama, berapa
banyak penawaran yang berbeda ada?
Dengan kata lain, di masing-masing
sesuai hanya kehormatan (A-10) yang unik, dan delapan peringkat yang lebih
rendah seperti 'x' kartu. Jawaban yang jelas adalah, "Siapa yang
peduli?" Tapi masalahnya adalah menarik. Sangat mudah untuk menentukan
jumlah penawaran ketika semua kartu yang unik:! (! 13) 52/4, tapi sekarang itu
menjadi tugas yang menakutkan dengan ada rumus yang tersedia, atau setidaknya
tidak ada yang saya bisa merancang. Untuk menemukan jawabannya, saya mengambil
keuntungan dari salah satu usaha konyol saya sebelumnya - menghitung dealprints
- dan kekerasan sedikit oleh komputer.
Pertama, mempertimbangkan masalah
partisi lima penghargaan dari satu setelan menjadi empat tangan. Tabel berikut
menunjukkan cara ini dapat dilakukan. (Jumlah dapat diverifikasi dengan rumus
sebagai sejumlah cara untuk mendistribusikan lima item dalam empat kelompok = 4
^ 5 = 1024.)
Untuk menjelaskan perhitungan,
pertimbangkan kasus ketika kehormatan didistribusikan 3-1-1-0. Tiga penghargaan
dapat dipilih di 10 cara (5C3), kehormatan selanjutnya dapat dipilih dengan 2
cara (2C1), maka penghormatan terakhir dipaksa. Ini berarti ada 10 × 2 = 20
kombinasi untuk setiap distribusi tertentu. Karena pola 3-1-1-0 memiliki 12
permutasi, ada 20 × 12 = 240 Total kombinasi. Kasus-kasus lainnya ditentukan
sama.
Langkah selanjutnya adalah
menentukan berapa banyak di atas 1.024 kombinasi akan masuk ke masing-masing
dari 39 distribusi jas generik. Misalnya, jika gugatan dibagi 4-4-3-2, jelas
bahwa tidak ada 5-0-0-0 kombinasi yang mungkin karena Anda tidak dapat
menempatkan lima kartu di satu tangan. Selanjutnya, perlu untuk memeriksa
setiap permutasi secara terpisah sejak gugatan dibagi, katakanlah, 5-4-3-1 akan
menerima hanya setengah dari 4-1-0-0 kombinasi. Ini menghasilkan tabel berikut.
Apa tabel di atas menunjukkan
adalah sejumlah cara lima kehormatan dapat didistribusikan untuk setiap
distribusi jas. Misalnya, untuk setiap pola 4-4-3-2 jas, ada 900 cara untuk
mendistribusikan kartu kehormatan. Delapan kartu tempat hanya akan mengisi
ruang yang tersisa, tetapi ini tidak bisa dibedakan per kondisi masalah.
Semua yang tersisa adalah, untuk
setiap dealprint tertentu, untuk mencari empat pola gugatan di tabel di atas
dan memperbanyak faktor yang sesuai untuk menentukan jumlah penawaran yang
mungkin untuk dealprint itu; kemudian menambahkan total untuk semua dealprints.
Mengingat ada 37.478.624 dealprints tertentu, ini masih merupakan tugas berat.
Untungnya, itu sepotong kue untuk komputer. Butuh beberapa jam untuk menulis
dan debug program, tetapi sekali menjalankannya kembali jawabannya dalam waktu
sekitar 15 detik:
800,827,437,699,287,808
Jadi, ada lebih dari 800 kuadriliun penawaran yang berbeda jika kartu spot (2-9) di masing-masing sesuai dianggap sama. Hal ini mungkin tampak seperti banyak, dan itu pasti, tapi itu sangat kecil dibandingkan dengan 53+ octillion mungkin penawaran jembatan.
Kasus
Generalized
Masalah ini dapat digeneralisasi
untuk jumlah kartu yang unik di masing-masing sesuai, seperti dirangkum oleh
tabel berikut. The "Gugatan Makeup" menunjukkan penampilan
masing-masing sesuai, dengan asumsi kartu unik yang ditunjuk dari atas.
Mengamati bahwa dengan tidak ada
kartu yang unik (baris atas), jumlah penawaran sama dengan jumlah dealprints
tertentu. Juga mencatat bahwa tidak ada perbedaan antara 12 dan 13 kartu yang
unik; dalam kedua kasus itu menghasilkan jumlah penuh penawaran. Hal ini jelas
jika Anda berpikir tentang hal itu, karena dengan kartu hanya satu 'x', semua
kartu yang efektif yang unik.
Sekarang, jika seseorang dapat
menunjukkan formula mana saya bisa pasang di, mengatakan, 7 sebagai jumlah
kartu yang unik (dan nilai-nilai lain yang sesuai seperti 52, 13, dan 4) untuk
menghasilkan jawaban 5197480921767366548160, saya akan benar-benar terkesan.
Referensi :http://www.rpbridge.net/7z74.htm
Tidak ada komentar:
Posting Komentar