Prinsip Inklusi-Eksklusi

September 15, 2010

Prinsip Inklusi-Eksklusi

Filed under: Algoritma, Himpunan, Matematika — Hendra Jaya @ 6:41 am

Problem

Berapa jumlah bilangan kelipatan 2 atau 3 di bawah 1 juta?
Berapa jumlah bilangan kelipatan 2 atau 3 di bawah 10 juta?
Berapa jumlah bilangan kelipatan 2 atau 3 di bawah 100 juta?
Berapa jumlah bilangan kelipatan 2 atau 3 di bawah 1 milyar?
Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 di bawah 1 juta?
Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 di bawah 10 juta?
Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 di bawah 100 juta?
Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 di bawah 1 milyar?
Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 atau 7 di bawah 1 juta?
Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 atau 7 di bawah 10 juta?
Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 atau 7 di bawah 100 juta?
Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 atau 7 di bawah 1 milyar?
dst…

Post Terkait : Barisan Bilangan 1 : Deret Aritmatika
Bahan : Deret Aritmatik, Prinsip Inklusi-Eksklusi

Teammate Perspectives

Pembahasan

Ada satu prinsip yang perlu dikuasai untuk menjawab pertanyaan-pertanyaan di atas. Namanya Prinsip Inklusi-Eksklusi. Hal penting yang mungkin lupa diajarkan oleh bapak/ibu guru kita di sekolah. Untuk memahami penjelasan mudahnya, perhatikan contoh di bawah ini :

$\begin{array}{lllllllllllllllllll}&&&&S(3)&=&S(3)\\&&S(3)&\cup&S(5)&=&S(3)&+&S(5)&-&S(3.5)\\S(3)&\cup&S(5)&\cup&S(7)&=&S(3)&+&S(5)&+&S(7)&-&S(3.5)&-&S(3.7)&-&S(5.7)&+&S(3.5.7)\end{array}$

Tanda (+) : 3, 5, dan 7
Tanda (-) : 15, 21 dan 35
Tanda (+) : 105
dst…

Secara umum, semua kombinasi “orde” ganjil akan bertanda positif dan semua kombinasi “orde” genap akan bertanda negatif. Untuk pembuktiannya silahkan kunjungi link yang penulis berikan di atas. Yang dimaksud orde disini adalah “jumlah faktor”. Misalnya, 15 = 3.5. Artinya 15 adalah orde 2 (genap) dan akan bertanda negatif. Sedangkan 105 = 3.5.7 adalah orde 3 (ganjil) dan akan bertanda positif.

Desain Algoritma

Asumsi 1 : Setiap bilangan pada input adalah bilangan bulat positif.
Asumsi 2 : Setiap bilangan pada input saling koprima (FPB-nya 1) dengan bilangan lainnya.

Siapkan sebuah array dengan ukuran yang cukup untuk menampung semua kombinasi bilangan. Jumlah kombinasi yang mungkin adalah $2^n-1$ . Dikurangi 1 karena kita tidak menangani kombinasi kosong.

Negasikan setiap bilangan pada input sehingga menjadi bilangan negatif (-).
Kalikan setiap bilangan (negatif) ini dengan semua bilangan lainnya yang ada pada array.
Hasil perkaliannya letakkan di bagian array yang masih kosong.

Catatan : Bagian array yang “baru saja” ditulisi dengan hasil perkalian jangan dibaca. Cukup baca isi array sebelum bilangan (negatif) ini “datang”.

Jika sudah tidak ada lagi bilangan yang ingin dikalikan. Maka letakkan versi awal (versi positif) dari bilangan ini ke dalam tempat yang masih kosong.

Lakukan terus sampai input habis.

Contoh

Kita akan mencari kombinasi dari $\{2,3,5\}$ lengkap dengan inklusi-eksklusi-nya

Ukuran input : $n=3$
Ukuran array : $2^n-1=2^3-1=8-1=7$

Kondisi sebelum input pertama (2) :

Array : [-1, -1, -1, -1, -1, -1, -1]
Slot kosong : 1

Proses input pertama (2) :

Tidak ada elemen sebelumnya.
Letakkan 2 di slot 1. Sehingga array menjadi [2, -1, -1, -1, -1, -1, -1], slot kosongnya sekarang di 2.

Kondisi sebelum input kedua (3) :

Array : [2, -1, -1, -1, -1, -1, -1]
Slot kosong : 2

Proses input kedua (3) :

Kalikan -3 dengan 2 = -6.
Letakkan -6 di slot 2. Sehingga array menjadi [2, -6, -1, -1, -1, -1, -1], slot kosongnya sekarang di 3
Elemen sebelumnya habis.
Letakkan 3 di slot 3. Sehingga array menjadi [2, -6, 3, -1, -1, -1, -1], slot kosongnya sekarang di 4

Kondisi sebelum input ketiga (5) :

Array : [2, -6, 3, -1, -1, -1, -1]
Slot kosong : 4

Proses input ketiga (5) :

Kalikan -5 dengan 2 = -10.
Letakkan -10 di slot 4. Sehingga array menjadi [2, -6, 3, -10, -1, -1, -1], slot kosongnya sekarang di 5
Kalikan -5 dengan -6 = 30.
Letakkan 30 di slot 5. Sehingga array menjadi [2, -6, 3, -10, 30, -1, -1], slot kosongnya sekarang di 6
Kalikan -5 dengan 3 = -15.
Letakkan -15 di slot 6. Sehingga array menjadi [2, -6, 3, -10, 30, -15, -1], slot kosongnya sekarang di 7
Elemen sebelumnya habis
Letakkan 5 di slot 7. Sehingga array menjadi [2, -6, 3, -10, 30, -15, 5], tidak ada slot kosong lagi

Input habis

Technical Jibba-Jabba

Pseudocode algoritma Gauss :

PseudoCode

Pseudocode algoritma Inklusi-Eksklusi Iteratif :

PseudoCode

Pseudocode algoritma Inklusi-Eksklusi Rekursif (Oleh Peter Harjanto) :

PseudoCode

Implementasi Java Iteratif : Ideone , PDF
Implementasi Java Rekursif : Ideone
Implementasi C++ : sabar, lagi dibuat

Benchmark

Algoritma 1 : Algoritma Konvensional (Brute Force)
Algoritma 2 : Algoritma Gauss + Prinsip Inklusi-Eksklusi (Versi Iteratif)
Algoritma 3 : Algoritma Gauss + Prinsip Inklusi-Eksklusi (Versi Rekursif)
Mesin 1 : Intel Celeron 1.5 GHZ + Windows XP SP3 + Java 1.6.0.13 (Laptop pribadi)
Mesin 2 : Intel(R) Pentium(R) 4 CPU 3.20GHz + Unknown OS + Java 1.6.0.17 (Ideone – Unofficial Information)

Benchmark Algo Konvensional vs Algo Gauss + Inklusi-Eksklusi

Catatan : Algoritma 1 tidak dites di mesin 2 (Ideone) karena mesin 2 hanya mengizinkan program untuk berjalan selama maksimal 15 detik.
Catatan : Algoritma 3 tidak dites karena ide dasarnya sama dengan algoritma 2. Yang membedakan hanya implementasi yang menggunakan teknik rekursif atau iteratif.

Hindsight into Foresight

Like this:

Be the first to like this post.

Komentar (2)

2 Komentar »

Cerdik pakai array.
Kalau aku sih pasti langsung terpikir pakai rekursif untuk meng-generate kombinasinya.
My pseudo code:

data[] = {2,3,5} List result
function gen(int level, int index, int jumlah) if (level ganjil) then result.add(jumlah) else result.add(-jumlah) if level > data.size then exit for i = index to data.size gen(level+1, i+1, jumlah * data[i]) end for end function gen(0,0,1)

blm kucoba sih, mungkin ada kesalahan. bikinnya cepat2

Komentar oleh Peter Aloysius — September 15, 2010 @ 7:38 am

Balas
- Yap. It works Pet. Tinggal ngejaga bahwa angka ’1′ tidak dihitung.
  
  Komentar oleh Hendra Jaya — September 15, 2010 @ 10:45 am
  
  Balas