Permutasi dan Kombinasi dengan Python

 Permutasi

Pertama sekali untuk dapat melakukan permutasi di Python kita harus mengimpor fungsi permutations dari paket itertools. Fungsi permutations() menerima argumen list sebagai input dan mengembalikan sebuah list berisi semua permutasi yang mungkin.

Kombinasi

Fungsi combinations menerima argumen list dan sebuah bilangan r, dan mengembalikan daftar tuple dari semua kombinasi dengan panjang r yang mungkin.

jika n tidak jauh dari r maka menggunakan definisi kombinasi rekursif mungkin lebih baik, karena xC0 == 1 Anda hanya akan memiliki beberapa iterasi:

Definisi rekursif yang relevan di sini adalah:

nCr = (n-1) C (r-1) * n/r

Ini dapat dihitung dengan baik menggunakan rekursi ekor dengan daftar berikut:

[(n - r, 0), (n - r + 1, 1), (n - r + 2, 2), ..., (n - 1, r - 1), (n, r)]

yang tentu saja mudah dihasilkan dalam Python (kami menghilangkan entri pertama sejak nC0 = 1) oleh izip(xrange(n - r + 1, n+1), xrange(1, r+1)) Perhatikan bahwa ini mengasumsikan r <= n Anda perlu memeriksa untuk itu dan menukar mereka jika tidak. Juga untuk mengoptimalkan penggunaan jika r <n/2 maka r = n - r.

Sekarang kita hanya perlu menerapkan langkah rekursi menggunakan rekursi ekor dengan mengurangi. Kita mulai dengan 1 karena nC0 adalah 1 dan kemudian gandakan nilai saat ini dengan entri berikutnya dari daftar seperti di bawah ini.


1.    Untuk menghindari overflow, lakukan semuanya di ruang log. Gunakan fakta bahwa log (a * b) = log (a) + log (b), dan log (a/b) = log (a) - log (b). Ini membuatnya mudah untuk bekerja dengan faktorial yang sangat besar: log (n!/M!) = Log (n!) - log (m!), Dll.

2.    Gunakan fungsi gamma sebagai ganti faktorial. Anda dapat menemukannya di scipy.stats.loggamma. Ini adalah cara yang jauh lebih efisien untuk menghitung faktor-log dari penjumlahan langsung. loggamma(n) == log(factorial(n - 1)), dan demikian pula, gamma(n) == factorial(n - 1).


Komentar

Posting Komentar

Postingan populer dari blog ini

Aturan Penjumlahan

Gambar
 Mutually Exclusive Events Dua buah events A dan B adalah mutually exclusive events bila A dan B tidak dapat muncul pada waktu yang bersamaan.   Mutually Exclusive.  contohnya: misal kejadian A : Anto masuk sekolah, kejadian  B : Anto tidak masuk sekolah. Not Mutually Exclusive   Event A: Mendapatkan seorang mahasiswa pria dari pemilihan acak sekumpulan mahasiswa  Event B: Mendapatkan seorang mahasiswa fakultas kedokteran dari pemilihan acak sekumpulan mahasiswa   Aturan Penjumlahan P(A atau B)=P(A)+P(B) P(A∪B)=P(A)+P(B) Contoh kejadian pada saat kita melakukan tos dengan dua koin, dimisalkan akan muncul kejadian tepat 1 gambar (A) atau bisa juga tepat 2 gambar (B). Jika ditulis secara matematis dapat dimisalkan A = {(G, A), (A, G)} dan B = {{G, G)}. Terlihat bahwa tidak ada satupun elemen A yang sama dengan elemen B. Aturan penjumlahan terjadi apabila terdapat 2 kegiatan, misalkan kegiatan 1 terjadi sebanyak A cara dan kegiatan 2 terjadi sebanyak B ca...
Baca selengkapnya

Distribusi Binomial

Gambar
 Binomial experiment merupakan suatu probability experiment yang memenuhi kriteria berikut:  1. Memiliki jumlah percobaan (trials) yang tetap dan setiap trial independent terhadap trials lainnya.  2. Setiap trial hanya memiliki dua kemungkinan outcomes; biasa dikategorikan sebagai success (S) atau failure (F).  3. Memiliki nilai probability success yang sama untuk tiap trial. 4. Random variabel x merepresentasikan jumlah kemunculan success dalam suatu experiment. n = Banyaknya trials pada suatu experiment p = Nilai probability success pada suatu trial q = Nilai probability failure pada suatu trial    ( q = 1-p) x = Jumlah kemunculan success pada suatu experiment Binomial Probability Formula Terdapat beberapa cara untuk menghitung probability dari x success dari sejumlah n trials pada suatu binominal experiment: Tree Diagram, Multiplication Rule, Binomial Probability Formula. p(x) =    n C x . P^ x  . ( 1-P)^ n-x Binomial Probability...
Baca selengkapnya

Geometric Distribution & Poisson Distribution

  Geometric Distribution merupakan suatu discrete probability distribution yang memenuhi kriteria berikut:  1. Percobaan (trial) akan dilakukan berulang kali sampai mendapatkan outcome success.  2. Setiap percobaan (trial) adalah independent terhadap trials lainnya. 3. Memiliki nilai probability success (p) yang sama untuk tiap trial.  4. Random variable x merepresentasikan banyaknya trials yang dilakukan sampai mendapati kondisi success. q = 1 - p p(x) = p . q ^ x-1 Poisson Distribution merupakan suatu discrete probability distribution yang memenuhi kriteria berikut:  1. Random variable x merepresentasikan banyaknya kemunculan suatu event dalam interval waktu tertentu. 2. Nilai probability untuk kemunculan event adalah sama untuk setiap interval.  3. Jumlah kemunculan event pada suatu interval adalah independent terhadap jumlah kemunculan event pada interval lainnya. P(x; μ) = (e -μ  * μ x ) / x ! μ = 2 (jumlah rata-rata badai per tahun, secara hist...
Baca selengkapnya