Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Thursday, August 23, 2012
Sequences in sorted order
Given two integers k and n, write a function that prints all the
sequences of length k composed of numbers 1,2..n. You need to print
these sequences in sorted orde
Basically out of all the possible k-permutations you print just the sorted one. You can generate all the perms and skip printing the unsorted ones (but you'll generate n!(n-k)! strings and most of them will be not printed out) or you can just avoid to generate the unsorted ones and print the remaining.
Here the code for this second solution:
public static void printSortedPerm(List list, String str, int k, int top) {
if (k == 0) { System.out.println(str); } else { for(int i = 0; i < list.size(); i++) { if (list.get(i) < top) continue; Integer next = list.remove(i); printSortedPerm(list, str + next, k-1, next); list.add(i, next); } } }
// main List list = new ArrayList(); list.add(1); list.add(2); list.add(3); list.add(4); printSortedPerm(sortedList, "", 3, -1);
classical question to test how you play with recursion
ReplyDeleteBasically out of all the possible k-permutations you print just the sorted one. You can generate all the perms and skip printing the unsorted ones (but you'll generate n!(n-k)! strings and most of them will be not printed out) or you can just avoid to generate the unsorted ones and print the remaining.
ReplyDeleteHere the code for this second solution:
public static void printSortedPerm(List list, String str, int k, int top) {
if (k == 0) {
System.out.println(str);
}
else {
for(int i = 0; i < list.size(); i++) {
if (list.get(i) < top) continue;
Integer next = list.remove(i);
printSortedPerm(list, str + next, k-1, next);
list.add(i, next);
}
}
}
// main
List list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
printSortedPerm(sortedList, "", 3, -1);