Permutasi adalah suatu konsep, dimana kita harus menghitung berapa banyak grup yang bisa kita buat dari sejumlah element, dengan memperhatikan urutan element. Sebagai contoh, kita memiliki 2 buah element, yaitu huruf ‘a’ dan huruf ‘b’. Dengan menggunakan kedua element ini, maka kita bisa membuat 4 buah string, yaitu ‘aa’, ‘ab’, ‘ba’ dan ‘bb’.

Ada 2 jenis permutasi. Yang pertama adalah permutasi yang memperbolehkan element yang berulang. Disini kita bisa mendapatkan 4 hasil, karena memperbolehkan string yang dibentuk dari element yang berulang seperti ‘aa’ dan ‘bb’. Yang kedua adalah permutasi yang tidak memperbolehkan element yang berulang. Disini hasil seperti ‘aa’ tidak diperbolehkan karena element ‘a’ digunakan secara berulang.

Bagaimana cara menulis program untuk permutasi? Kita bahas secara teori dahulu ya. Algoritma yang digunakan disini adalah Backtracking. Disini kita melakukan pencarian solusi dengan menggunakan struktur data yang berbentuk tree, kita mulai dari level nol. Pada titik awal, kita buat cabang dengan semua element yang ada. Sebagai contoh disini kita menggunakan 2 element ya, yaitu ‘a’ dan ‘b’. Cabang kita taruh pada level berikutnya, yaitu level satu.

Selanjutnya, kita bergerak turun ke bawah, dimulai dari cabang yang berada di sebelah kiri. Jadi sekarang kita berada di posisi huruf ‘a’, level 1. Disini kita buat lagi cabang untuk semua kemungkinan yang ada, yaitu huruf ‘a’ dan huruf ‘b’ di level 2.

Setelah itu kita turun lagi ke cabang paling kiri di level 2. Posisi kita saat ini adalah ‘aa’. Huruf ‘a’ pada level 1 dan huruf ‘a’ lagi pada level 2. Berhubung kita sudah mencapai kedalaman yang paling ujung, maka kita mendapatkan hasil yaitu ‘aa’.

Setelah mendapatkan hasil, maka kita melakukan backtraking, yaitu kita kembali ke posisi level sebelumnya. Jadi kita kembali ke level 1 dengan posisi huruf ‘a’.

Dari sana kita turun lagi ke cabang berikutnya, sehingga posisi kita menjadi ‘ab’. Dan kita pun mendapatkan hasil kedua yaitu ‘ab’.

Kita lakukan backtracking, kembali ke posisi ‘a’ di level 1. Berhubung semua cabang telah diperiksa, maka kita lakukan lagi backtracking ke titik awal di level 0. Kita lakukan pemeriksaan di cabang berikutnya, yaitu di huruf ‘b’ level 1.

Kita buat dahulu semua kemungkinan yang ada, yaitu ‘a’ dan ‘b’ di level 2.

Lalu kita turun ke cabang kirinya, dan kita mendapatkan hasil ‘ba’. Kita backtracking kembali ke huruf ‘b’ di level 1. Dan kita turun lagi ke cabang berikutnya untuk mendapatkan hasil ‘bb’.

Nah, berhubung kita sudah berhasil memeriksa semua cabang, maka algoritma kita berakhir.

Sebagai latihan pada video ini, tuliskan script PHP untuk menyelesaikan masalah permutasi dengan menggunakan rekursif. Input yang diberikan berupa string ‘ab’. Artinya kita akan melakukan permutasi dengan menggunakan 2 element, yaitu huruf ‘a’ dan ‘b’.

Pertama buatlah dahulu permutasi yang memperbolehkan pengulangan. Permutasi ini akan memberikan 4 hasil ‘aa’, ‘ab’, ‘ba’ dan ‘bb’.

Nantinya kalau sudah berhasil mengerjakan tugas pertama, kita tinggal menambahkan 1 kondisi saja agar permutasi tidak memperbolehkan pengulangan. Permutasi yang kedua memberikan hasil ‘ab’ dan ba’.

Pause terlebih dahulu video ini dan coba kerjakan latihan pada komputer masing-masing. Kita akan kembali untuk membahas solusinya.

Kita mulai kerjakan soal latihan kita ya. Kita buat function permutation yang akan dipanggil secara rekursif. Parameter pertamanya bertipe data string, kita beri nama $elements yang akan diisi dengan element-element yang bisa digunakan untuk permutasi. Parameter kedua adalah string $position, yang berfungsi untuk menunjukkan posisi kita di dalam tree. Sedangkan parameter ketiga adalah string $newElement, yang menunjukkan cabang baru yang sedang kita periksa. Untuk parameter $position dan $newElement kita berikan nilai default berupa string kosong.

Di dalam function, artinya setiap kali kita mencapai level baru, maka yang perlu kita lakukan adalah menambahkan posisi sekarang dengan elemen baru. Kita bisa tulis kodenya menjadi

$position .= $newElement

Kemudian kita tuliskan base case dari rekursif ini. Apa yang menyebabkan kita keluar dari rekursif? Jawabannya adalah kalau kita sudah mencapai level paling bawah. Kalau dilihat dari slide barusan, level paling bawah adalah 2, dimana posisi kita menunjukkan 2 huruf. Sedangkan soalnya juga terdiri dari 2 huruf.

Jadi untuk base case, kita bandingkan apabila strlen dari $position sudah sama dengan strlen dari $elements. Apabila benar, maka kita sudah mencapai level paling bawah dari tree. Jadi kita tinggal echo $position sebagai hasil jawaban kita. Kemudian kita panggil return untuk keluar dari function.

Selanjutnya. Pada saat kita mencapai level baru. Apa yang harus kita lakukan? Kita harus membuat cabang di level berikutnya. Cabang ini terdiri dari setiap huruf di dalam $elements. Untuk mengambil setiap huruf di dalam $elements, maka kita mesti membuat looping.

for($i = 0; $i < strlen($elements); $i++)

Huruf kita simpan sebagai $newElement. Bagaimana cara mengambil huruf dari string? Kita gunakan index ke $i.

$newElement = $elements[$i]

Setelah itu kita panggil lagi fungsi permutation dengan argument $elements, $position, dan $newElement. Perhatikan disini nilai $position telah berubah karena pada awal fungsi kita sudah menambahkan $position dengan $newElement. Sedangkan nilai dari $newElement kita ambil dari masing-masing huruf yang dikandung oleh string $elements.

Function kita sudah selesai. Kita coba panggil dengan argument ‘ab’. Maka kita mendapatkan 4 hasil, yaitu ‘aa’, ‘ab’, ‘ba’, ‘bb’.

Kita sudah berhasil mengerjakan soal permutasi yang memperbolehkan perulangan element. Kita lanjutkan ke permutasi kedua. Kalau permutasi tidak memperbolehkan perulangan, maka kita hanya perlu menambahkan satu buah kondisi. Kondisi ini bisa kita taruh di sebelum pemanggilan permutation secara rekursif. Kita periksa dahulu apakah $newElement sudah pernah digunakan di dalam $position atau belum. Kita bisa gunakan fungsi str_contains dengan argument $position dan $newElement. Kita hanya memanggil function permutation secara rekursif apakah hasil dari str_contains adalah false, oleh karena itu kita tambahkan tanda seru sebelum nama function-nya.

Kita jalankan dan kita hanya mendapatkan hasil ‘ab’ dan ‘ba’. Kita bisa coba juga function permutation ini untuk string lain seperti ‘abc’ ya. Yang penting semua huruf di dalam string $elements ini tidak boleh ada yang berulang, karena algoritma kita pada saat ini tidak bisa digunakan untuk nilai awal elements yang berulang.

Dengan menggunakan fasilitas tanya jawab, maka Anda bisa bertanya dan akan dijawab langsung oleh instruktur kursus.

Anda belum terdaftar pada kursus ini sehingga tidak bisa mengajukan pertanyaan.