PENENTUAN NILAI PERMUTASI DENGAN LEXICOGRAPHIC ORDER

Permutasi tanpa perulangan, biasa dirumuskan dengan n!
Jumlah Permutasi ini ada n!
Misal, permutasi n = 5,
P5= 5! = 120
120 tersebut merupakan barisan angka yang berbeda satu sama lain, dari masing-masing barisan angka, terdapat 5 digit angka yang berbeda. Inilah kenapa disebut permutasi tanpa perulangan.

Dalam prakteknya permutasi tanpa perulangan sering dipakai dalam teori graf, matematika diskrit, peluang, teori antrian, dll

Nah untuk mencari semua nilai barisan angka dari permutasi tanpa perulangan,
bisa kita pakai manual, yaitu dengan bolak-balik angka, tuker-tuker tempat, cari pola, sampe ketemu 120 barisan angka yang berbeda.
bisa juga dengan komputasi, yaitu mencari algoritma yang rasional dan dibuatlah beberapa perintah baris program sehingga hasilnya komputer dapat mencari sendiri nilai dari 120 permutasi tersebut.

P5= 5! = 120
1-2-3-4-5
2-3-4-5-1
3-4-5-1-2
dst

Dengan menggunakan fungsi rekursif sederhana, hal ini dapat di implementasikan dalam program komputer:


var dgt;
var permutations;
    function permRekursif(dgt) {  
        /* Jika hanya memiliki panjang karakter tunggal, maka kembalikan nilai string */  
       if (strlen(dgt) < 2) {  
          return array(dgt);  
       }  
      
        /* Inialisasi variabel menjadi array */  
        permutations = array();  
      
       /* ambil nilai dari dgt, kecuali angka pertama */  
       ekor = substr(dgt, 1);  
    
       /* ulangi permutasi dengan dgt ekor */  
       foreach (permRekursif(ekor) as permutation) {  
           /* cari panjang permutation */  
          length = strlen(permutation);  
           /* konstruk permutasi dengan memasukkan bil pertama diantara dua blok bilangan sampai ketemu panjang < 2*/  
           for (i = 0; i <= length; i++) {  
               permutations[] = substr(permutation, 0, i) . dgt[0] . substr(permutation, i);  
           }  
       }  
    
       /* kembalikan nilai array dari hasil permutasi */  
       return permutations;  
    }  
 
//cara manggilnya
permRekursif(jumDgt);


Nah, masalahnya akan muncul jika yang di input adalah digit yang besar, contohnya
n = 20 atau n = 30
n! = 20! = 2432902008176640000
n! = 30! = 2.6525285981219103e+32

Apakah komputer dual core anda ngatasin? pastinya baru 10 digit dengan pemrosesan 3628800 kali data sudah hang.
yang kita harapkan adalah penyelesaian permutasi dengan n digit, berapapun nilainya.

keterbatasan komputer bisa kita tutupi dengan kecerdasan logika, dimana perulangan milyaran kali tidak bisa diselesaikan sekali proses, namun bisa dilakukan one by one sehingga nilai permutasi dapat di generate dengan ringan oleh komputer anda, bahkan yang pentium 1 sekalipun.

Metode penyelesaian permutasi one by one, bisa pakai lexicographic order, dimana barisan angka diurutkan berdasarkan dari kecil ke besar, mirip seperti bikin kamus, dari a, b, c sampai z.
makanya metode ini disebut juga dengan dictionary order.

Nah, misal n=3
hasil permutasi dengan metode LO ini menghasilkan
123
132
213
231
312
321
persis, urut dari kecil ke besar.

Sekarang kita ingin mencoba mencari algoritma dari lexicographic order, sehingga jika kita kirim angka ke -i dia mengirim nilai yang kita maksud.
misalkan dalam n=3 tadi,
kita kirim angka 3, maka dia mengembalikan nilai 213
kita kirim angka 5, maka dia mengembalikan nilai 312
Bisa nggak kira-kira komputer menyelesaikan ini?
pasti bisa donk, ngapain di bahas kalau ga bisa.

wah udah panjang ya… diterusin nanti di episode berikutnya oke coy…sabar sabar…