Combinatorics dengan Python

Pustaka python standar, dimulai dengan versi 2.2, menyediakan banyak alat untuk menghasilkan objek kombinatorial, tetapi saya tidak dapat menemukan satu artikel pun di Internet yang akan menjelaskan secara detail tentang cara bekerja dengannya. Oleh karena itu, saya memutuskan untuk memperbaiki kekurangan ini.

Untuk mulai dengan, saya akan berbicara tentang kombinatorik dan formula dasarnya. Jika Anda sudah terbiasa dengan bagian matematika ini, Anda dapat melewati paragraf ini.

Misalkan kita memiliki string yang terdiri dari n huruf yang berbeda dan kami ingin menghitung semua cara untuk mengatur ulang surat-surat ini sedemikian rupa untuk mendapatkan baris baru. Untuk posisi pertama dalam barisan, kita dapat memilih salah satu dari n huruf yang kita miliki, untuk posisi kedua salah satu dari huruf ke-1 dan seterusnya. Akibatnya, kami memperoleh produk n (n-1) ... * 1 = n! jumlah permutasi dari n elemen tanpa pengulangan .

Sekarang bayangkan bahwa jumlah huruf dalam string terbatas. Kami memiliki n huruf yang tersedia dan kami ingin menghitung jumlah cara untuk membuat string dengan panjang k dari mereka, di mana k <n, kita dapat menggunakan setiap huruf hanya sekali. Kemudian kita dapat meletakkan salah satu dari n huruf pada posisi pertama di baris, salah satu dari huruf n-1 di posisi kedua dan salah satu dari huruf n-k + 1 pada posisi k-th. Jumlah total garis akan sama dengan n (n - 1) (n - 2) ... (n - k + 2) (n - k + 1) = n! / (Nk)! jumlah penempatan dari n ke k . Jika keunikan huruf tidak diperlukan, maka kami memperoleh rumus n ... n n = n ^ k jumlah penempatan dari n ke k dengan pengulangan .

Sebelum itu, kami memilah-milah urutan dengan mempertimbangkan urutan elemen, dan bagaimana jika urutan tidak masalah bagi kami. Misalnya, kami memiliki n permen yang berbeda dan kami ingin memilih k dari mereka untuk diberikan kepada teman, dan k <n. Berapa banyak cara yang ada untuk memilih k permen dari n tanpa memperhatikan pesanan? Jawabannya sederhana, pada awalnya kita akan menemukan penempatan n oleh k tanpa pengulangan, tetapi kemudian set permen yang sama memiliki urutan urutan yang berbeda akan diulang. Berapa banyak cara yang ada untuk mengatur ulang permen k? Itu benar, permutasi elemen k tanpa pengulangan. Jawaban terakhir: penempatan n oleh k dibagi dengan permutasi k tanpa pengulangan. Formula $$$n! / (n-k)! / k!$jumlah kombinasi n oleh k .

Pertimbangkan kasusnya yang lebih rumit, kami memiliki n kotak yang masing-masing berisi banyak permen dengan rasa yang sama, tetapi dalam kotak yang berbeda rasanya berbeda. Berapa banyak cara yang ada untuk membuat hadiah kepada teman dari permen, dan apa yang bisa merasakan hal yang sama beberapa kali? Karena pesanan itu tidak masalah bagi kami, mari kita mengatur permen hadiah sebagai berikut: pada awalnya akan ada permen berturut-turut dari rasa pertama, lalu yang kedua dan seterusnya, dan kami akan menempatkan korek api di antara permen dengan selera yang berbeda jika tidak ada permen dengan rasa apa pun dalam hadiah kami - korek api yang seharusnya membatasi rasa ini di sebelah kiri dan di sebelah kanan akan berdiri berdampingan. Selain itu, kami mendapatkan urutan yang terdiri dari k sweets dan n-1 match, karena hanya ada n taste, dan match memisahkan mereka. Sekarang perhatikan bahwa dengan lokasi pertandingan, kita dapat mengembalikan set asli. Maka jawabannya adalah jumlah cara untuk menempatkan kecocokan n-1 dalam sel n + k-1 tanpa memperhitungkan urutannya, yang sama dengan jumlah kombinasi n + k-1 dengan n-1, rumus: $$$(n + k-1)! / k! / (n-1)!$jumlah kombinasi n hingga k dengan pengulangan .

Sekarang kita akan mempertimbangkan beberapa masalah pada kombinatorik untuk mengkonsolidasikan materi.

Tugas 1

Ada 20 orang, ada berapa cara untuk memasangkan mereka
Solusi: ambil orang pertama, berapa banyak cara untuk memilih pasangan untuknya: $$$20-1 = 19$, ambil orang kedua, berapa banyak cara untuk memilih pasangan untuknya: $$$20-2-1 = 17$. Jawab: 19 !!! = 654729075

Tugas 2

Ada 10 laki-laki dan 10 perempuan, berapa banyak cara untuk memecah mereka menjadi perusahaan yang terdiri dari jumlah laki-laki dan perempuan yang sama, sebuah perusahaan kosong tidak dianggap
Solusi:
Metode 1: jumlah cara untuk mengumpulkan perusahaan dari satu laki-laki dan satu perempuan sama dengan produk dari jumlah cara untuk memilih satu perempuan dan jumlah cara untuk memilih satu laki-laki. Jumlah cara untuk memilih satu gadis dari 10 sama dengan kombinasi 10 hingga 1 tanpa pengulangan, itu sama dengan laki-laki, jadi kami akan jujur. Selanjutnya, kami juga menghitung kombinasi 10 hingga 2, dari 10 hingga 3, dan seterusnya ke kombinasi 10 hingga 10. Rumus terakhir: $$$(10! / (10-1)! / 1!) ^ 2 + (10! / (10-2)! / 2!) ^ 2 + ... + (10! / (10-10)! / 10!) ^ 2$.
Metode 2: pertimbangkan banyak pria yang ada di perusahaan dan banyak wanita yang tidak ada di perusahaannya. Untuk set ini, Anda pasti dapat memulihkan perusahaan, dan jumlah orang di dalamnya selalu sama dengan 10, karena $$$k + (10 - k) = 10$, k - jumlah pria di perusahaan, $$$10 - k$- jumlah gadis yang tidak termasuk di dalamnya. Jumlah set tersebut sama dengan jumlah kombinasi 20 hingga 10, pada jawaban akhir kita juga akan mengurangi satu sehingga tidak memperhitungkan perusahaan kosong ketika ada 10 gadis di set kami. Rumus terakhir: $$$20! / (20-10)! / 10! - 1 = $ 18475$.

Jadi, kita menemukan teorinya, sekarang kita akan belajar bagaimana menghasilkan objek kombinatorial menggunakan pustaka python standar.
Kami akan bekerja dengan perpustakaan itertools

from itertools import * 

Menggunakan fungsi permutasi , Anda bisa menghasilkan semua permutasi untuk objek yang dapat diulang.

Contoh 1

 for i in permutations('abc'): print(i, end=' ') # abc acb bac bca cab cba print() for i in permutations('abb'): print(i, end=' ') # abb abb bab bba bab bba 

Berdasarkan panggilan kedua, kami mencatat bahwa elemen yang sama di posisi yang berbeda dianggap berbeda.

Contoh 2

 for i in permutations('abc', 2): print(i, end=' ') # ab ac ba bc ca cb 

Penempatan berbeda dari permutasi dengan batas jumlah sel yang tersedia

Contoh 3

 for i in product('abc', repeat=2): print(i, end=' ') # aa ab ac ba bb bc ca cb cc 

Dengan tata letak pengulangan, Anda dapat dengan mudah beralih pada semua string panjang tetap yang terdiri dari karakter yang diberikan

Contoh 4

 for i in combinations('abcd', 2): print(i, end=' ') # ab ac ad bc bd cd 

Menggunakan kombinasi tanpa pengulangan, Anda dapat mengulangi semua set huruf yang tidak berulang dari string, array, atau objek lain yang dapat diulang tanpa memperhatikan urutan

Contoh 5

 for i in combinations_with_replacement('abcd', 2): print(i, end=' ') # aa ab ac ad bb bc bd cc cd dd 

Hasilnya mirip dengan kombinasi panggilan, tetapi set dengan elemen yang sama juga ditambahkan ke hasilnya.

Bahan:
N.V. Gorbachev "Koleksi masalah olimpiade dalam matematika"
Dokumentasi python dalam bahasa Rusia