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);