Enumerating Gene Orders (Rosalind)

 

Halo teman-teman, apa kabar? Kali ini saya ingin membahas sedikit tentang salah satu problem yang ada di web rosalind.info. Judulnya ialah "Enumerating Gene Orders". Sebagai acuan, teman-teman bisa cek dahulu problem yang akan kita bahas (disini). 

Di problem ini kita akan disajikan sebuah integer (sebut saja n) yang mewakili jumlah set angka yang masing-masing berbeda (contoh,  5 = [1, 2, 3, 4, dan 5]). Tugas kita ialah menemukan jumlah total permutasi yang bisa dibentuk dari set tersebut dan menyebutkan semua permutasinya. 

Untuk pengerjaan, pertama kita cari jumlah total permutasi menggunakan rumus faktorial n. 

Kemudian, untuk menyebutkan permutasinya, kita bisa menggunakan algoritma permutasi. Untuk lebih ditailnya, teman-teman bisa melihat referensi video yang ada disini. 

Berikut kode pengerjaannya dalam bahasa java :

1. static void nextPermutaion (int n, int[] arr) {
2. for (int x : arr) {
3. out.print(x + " ");
4. }
5. out.println();
6. while (true) {
7. int por = n - 2;
8. while (por >= 0 && arr[por] >= arr[por + 1]) {
9. por--;
10. }
11. if (por < 0) {
12. return;
13. }
14. for (int i = n - 1; i > por; i--) {
15. if (arr[i] > arr[por]) {
16. int swap = arr[por];
17. arr[por] = arr[i];
18. arr[i] = swap;
19. break;
20. }
21. }
22. for (int i = por + 1; i < (n + por + 1) / 2; i++) {
23. int swap = arr[i];
24. arr[i] = arr[n - 1 - (i - (por + 1))];
25. arr[n - 1 - (i - (por + 1))] = swap;
26. }
27. for (int x : arr) {
28. out.print(x + " ");
29. }
30. out.println();
31. }
32. }
33. static int factorial (int n) {
34. int res = 1;
35. for (int i = 1; i <= n; i++) {
36. res *= i;
37. }
38. return res;
39. }
40. static void solve() {
41. int n = ni();
42. int[] arr = new int[n];
43. for (int i = 0; i < n; i++) {
44. arr[i] = i + 1;
45. }
46. out.println(factorial(n));
47. nextPermutaion(n, arr);
48. }    
     

Kita mulai dari baris ke 40 (static void solve()). 

Seperti yang sudah dijelaskan, pertama kita mencari jumlah permutasi menggunakan rumus faktorial n (baris 33-39). 

Setelah itu, kita lanjutkan dengan menyebutkan semua permutasinya menggunakan algoritma permutasi (baris 1-32). Algoritma ini mirip dengan heap sort dan heap's algorithm: secara umum, kita hanya menukar-nukar angka di set tersebut dan mendapatkan semua permutasinya. Untuk lebih detailnya, teman-teman bisa membaca tentang heap's algorithm terlebih dahulu. 

Seperti yang teman-teman lihat; disini, saya memakai fungsi ni() (baris 11) untuk meng-input data integer. Fungsi tersebut adalah extend dari salah satu sistem input di java, yaitu BufferedReader. 

Sedangkan untuk output-nya saya memakai fungsi out.println() (baris 46). Fungsi tersebut juga adalah modifikasi dari fungsi System.out.println() yang merupakan fungsi default di java. Untuk lebih jelasnya, teman-teman bisa melihat kode tambahan untuk memodifikasi fungsi tersebut (input maupun output) di versi lengkap kode saya di github. 

Sekian dari saya. Jika teman-teman ingin menanyakan sesuatu, teman-teman bisa menulisnya di kolom komentar. Semoga bermanfaat dan sampai jumpa di artikel berikutnya!

Referensi :

Sumber gambar 1 :https://www.facebook.com/ProjectRosalind/