Tag

, ,

[Soal ini sudah saya sampaikan di halaman Facebook saya dan menuai banyak komentar. Sekarang sata dokumentasikan di sini.]

Ceritanya saya diminta untuk mencari himpunan permutasi 4 bilangan x1, x2, x3, x4 yang jumlah keempatnya adalah s (misalnya 27). Rentang bilangan xn adalah 0 sampai dengan 9. Adakah algoritma yang efisien untuk mencari solusi tersebut? (Catatan: tadinya di dalam postingan saya di Facebook, saya menyebutkan kombinasi bukan permutasi.)

Di halaman facebook saya banyak solusi yang diusulkan. (Terima kasih.) Bahkan ada yang sudah menampilkan snippet kode.

Secara visual, soal ini dapat dilihat seperti gambar berikut. (Maaf kalau gambarnya kurang jelas. Maklum ini corat-coret di buku.) Siapa tahu dengan gambaran secara visual dapat diperoleh pemahaman yang lebih baik.

masalah matematika

Bayangkan jika kita harus berjalan dari sisi kiri ke sisi kanan melewati 4 lapisan. Setiap titik memiliki biaya (cost) mulai dari 9 sampai dengan 0. Kita harus mencari jalan (path) yang nilainya sesuai dengan yang kita inginkan, seperti dala contoh adalah angka 27. Salah satu jalurnya adalah {7, 7, 7, 6}.

Nah selamat mencoba.

[Catatan: masalah ini merupakan bagian dari penelitian kami tentang anonimitas dalam e-voting.]