Enumerating Gene Orders (Rosalind | English)

Hi everyone, how are you? This time, I want to discuss with you about one problem (bioinformatics problem) that exist in rosalind.info's web. The title is "Enumerating Gene Orders". For the reference, you can first check out the problem that will be discussed (here). 

Overview

In this problem, we will given an integer (let's call it n) that representing a number of set of integers that every integer is unique; for example, n = 5 is [1, 2, 3, 4, 5]. Our task is to find the total number of permutation that can been formed from that set and then mention all of those permutations. 

For solving this problem, we can first find the total number of permutation by counting the n factorial. 

Then, for mentioning those permutations we can use the permutation algorithm. For details, you can see this video for the reference. 

The Code 

This is the code for solving this problem (with java language): 

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. }    
     

We start from line 40 (static void solve()). 

As what I've been explained, first, we calculate the total number of permutation using n factorial (line 33-39). 

After that, we continue by mentioning all of the permutation using the permutation algorithm (line 1-32). This algorithm is quite similar to heap sort and heap's algorithm: in general, we just swapping those integers until we meet all of those permutation. More technically, you can check a reference about the heap's algorithm here. 

Input and Output

In the code above, I used ni() function for entering the integer-form data (line 41). That function is an extension of one of the system inputs which are available in java; called BufferedReader. 

And for the output I used out.println() function (line 46). That function is a modification from System.out.println() function which is very familiar in java. You can see the additional code for that modification (input and output) in my complete code at github. 

That's it. If you want to ask something, you can write it in the comment section below. I hope this article is useful and see you in the next article! 

Reference :

Source of image 1 :https://www.facebook.com/ProjectRosalind/