Enumerating k-mers Lexicographically (Rosalind | English)

        

   

Hi everyone, how are you? This time, I want to discuss a little bit about a bioinformatics problem that exists in rosalind.info's web. The title is "Enumerating k-mers Lexicographically". For the reference, you can first check out the problem that will be discussed (here). 

Overview 

In this problem, we will given a several alphabet characters (the amount is unknown) and an integer; let's call them array alfa[ ] and integer n. 

Our task is to make string permutation consists of n letters that picked from alfa[ ]. In other words, we will make all of the strings that can be formed from alfa[ ] by n letters. For example, the string permutation that can be formed from letter 'A', 'B', and 'C' with (n = 2) is: "AA", "AB", "AC", "BA", "BB", "BC", "CA", "CB", and "CC". 

The Code

This is the code for solving this problem using java language: 

1. static void diPrint (int[] res, Vector<Character> karakter) {
2. for (int x : res) {
3. out.print(karakter.get(x));
4. }
5. out.println();
6. }
7. static void solve() {
8. Scanner sc = new Scanner(System.in);
9. Vector<Character> karakter = new Vector<>();
10. int n = 0;
11. while (sc.hasNext()) {
12. String masuk = sc.next();
13. if (masuk.charAt(0) >= 'A' && masuk.charAt(0) <= 'Z') {
14. karakter.add(masuk.charAt(0));
15. }
16. else {
17. n = Integer.valueOf(masuk);
18. }
19. }
20. int karSize = karakter.size();
21. int[] res = new int[n];
22. boolean terus = true;
23. while (terus) {
24. diPrint(res, karakter);
25. for (int i = n - 1; i >= 0; i--) {
26. if (res[i] != karSize - 1) {
27. res[i]++;
28. break;
29. }
30. {
31. if (i == 0) {
32. terus = false; break;
33. }
34. res[i] = 0;
35. }
36. }
37. }
38. }      

The Description Code

First, we look at the static void solve() function (line 7). After we entering the input (line 11-19), we can go into the string permutation making process directly (line 23-37). Here, I make the string permutations using the array method: the array will transformed lexicographically in every while loop rotation; and in every rotation, the strings will be printed based on the numbers that exist in the array at that time (23-37). 

Input and Output

As you can see, in the code above I used next() function for entering the string-form dataset (line 12). 

I also used another input function called hasNext() (line 11) because of its ability to entering the unknown amount of data. 

While, in the output I used out.print() & out.println() function (line 3 & 5). That function is a modification function from System.out.print() & System.out.println() which is the default function in java. For more details, 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 image 1: https://www.facebook.com/ProjectRosalind/