Partisi Bilangan

Partisi dari suatu bilangan bulat (integer partition) ialah cara untuk menuliskan bilangan tersebut sebagai jumlah dari bilangan bulat positif. Sebagai contoh, 5 mempunyai 7 partisi, atau 5 dapat dipartisi dalam 7 cara, yaitu :

  1. 5
  2. 4 + 1
  3. 3 + 2
  4. 3 + 1 + 1
  5. 2 + 2 + 1
  6. 2 + 1 + 1 + 1
  7. 1 + 1 + 1 + 1 + 1

Fungsi partisi p(n) ialah  jumlah partisi yang bisa dimiliki oleh suatu bilangan bulat positif n. Sebagai contoh, p(4) = 5, yaitu :

  1. 4
  2. 3 + 1
  3. 2 + 2
  4. 2 + 1 + 1
  5. 1 + 1 + 1 + 1

Catatan : Partisi tidak memperhatikan susunan/penempatan bilangan dalam arti partisi 1 + 3 sama dengan partisi 3 + 1. Begitu pula partisi 1 + 2 + 1 dan 1 + 1 + 2 sama dengan partisi 2 + 1 + 1.

Algoritma berikut ini ditulis dalam bahasa Python yang bisa digunakan sebagai generator rekursif untuk menghasilkan semua partisi dari argumen n. Masing-masing partisi tersebut dinyatakan dalam urutan angka diletakan dalam [ ] yang akan dijumlahkan, misalnya untuk partisi dari 4 bisa ditulis sebagai berikut : [1,1,1,1], [1,1,2], [2,2], [1,3], [4].

def partitions(n):
	if n == 0:
		yield []
		return

	for p in partitions(n-1):
		yield [1] + p
		if p and (len(p) < 2 or p[1] > p[0]):
			yield [p[0] + 1] + p[1:]

Untuk versi Python tanpa generator, yield bisa diganti dengan print. Thanks to David Eppstein.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s