Permutasi dalam programming

Sebelum memahami permutasi dalam programming, kalian harus paham tentang rekursi maupun permutasi itu sendiri. Disini saya hanya akan menjelaskan tentang permutasi di dalam programming, karenanya saya asumsikan kalian telah mengerti rekursi ataupun permutasi sebelum membaca lebih lanjut. Disini saya akan mencoba menggunakan bahasa pemrograman Java.

Problem paling sederhana dari permutasi biasanya ialah menghitung berapa banyak cara untuk menyusun sebuah kata

Contohnya diberikan string “ABC”, hitunglah berapa banyak cara untuk menyusun kata dari huruf-huruf yang ada didalam string tersebut.

Kita tau jawabannya ialah 6, yaitu

ABC
ACB
BAC
BCA
CAB
CBA

lalu bagaimana membuat program untuk menyelesaikan masalah tersebut ?

Coba breakdown terlebih dulu permasalahan nya, kita bisa menggunakan pendekatan divide n conquer untuk problem ini.

Bila kita analisa lebih dalam, banyak cara menyusun string “ABC” dengan string “A” di posisi awal kata ialah banyak cara menyusun string “BC”.
“BC” = [“BC”, “CB”] ada 2 cara, sehingga semua kemungkinannya ialah “ABC” dan “ACB”.

Kita telah memecah problem tersebut menjadi lebih kecil lagi, tapi kita masih harus mencari tau bagaimana cara nya mencari semua permutasi dari string “BC” ? Kalian mungkin bisa langsung mengatakan cukup tukar posisi B dan C, maka dapat disimpulkan hanya ada 2 cara yaitu “BC” dan “CB”. Dapat disimpulkan, ketika panjang string nya 2 maka banyak cara menyusun nya juga pasti ada 2.

Berdasarkan asumsi diatas, maka kita telah mendapatkan base case dari problem tersebut, yaitu ketika sub string nya berukuran 2 maka sudah pasti ada 2 cara untuk menyusun string tersebut.

Karena di problem tersebut tidak menyatakan bahwa string “A” harus berada di posisi awal, maka kita hanya perlu menempatkan semua karakter di posisi awal dan menghitung subproblem nya, sehingga kita mendapatkan semua permutasi nya.

Dapat kita lihat berdasarkan kode diatas, kode tersebut mencoba melakukan looping tiap karakter di string untuk menempatkan karakter tersebut di awal kata.

Variable left dan right diatas hanya berguna untuk membentuk string dengan membuang karakter yang sekarang berada di posisi awal, misal “ABC” dengan “B” di posisi awal, maka value dari left ialah “A” dan value dari right ialah “C”.

contoh string “ABC”, maka penyelesaiannya ialah
“A” diawal kata ditambah hasil dari recursion(“BC”) + “B” diawal kata ditambah hasil recursion(“AC”) + “C” diawal kata ditambah hasil recursion(“AB”)

karena recursion(“BC”), recursion(“AC”) dan recursion(“AB”) hasilnya sama-sama 2, maka kita hanya perlu menjumlahkan nya yaitu 2 * 3 = 6.

Karena base case dan recursion case nya sudah ada, kita hanya perlu menggabungkan 2 potongan kode itu menjadi 1 buah fungsi

Apakah menurut kalian solusi diatas benar ?

Tidak, karena jika string yang dicari permutasi nya hanya berjumlah 1 karakter, maka fungsi tersebut menghasilkan output 0, padahal seharusnya 1. Contohnya, banyak cara menyusun kata dari string “A” ialah 1, tetapi fungsi tersebut menghasilkan nilai 0.

Jika kalian perhatikan lagi, kode tersebut terdapat kesalahan di base case nya, karena kita tidak memecah problem tersebut menjadi lebih kecil lagi. Karenanya konsep rekursi dan pemahaman divide n conquer sangat dibutuhkan untuk menyelesaikan problem ini. Base case yang tepat ialah ketika string tersebut kosong, maka hasil nya 1, karena banyak cara menyusun string kosong ialah 1.

Time Complexity

O(n!)

Untuk time complexity nya ialah n!, karena di tiap function call, kita perlu melakukan function call sebanyak n dimana n ialah size atau banyak karakter dari string

Space Complexity

O(n)

Untuk menentukan space complexity dari recursive function, kita hanya perlu menghitung level (maximum depth) dari recursion tree.