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
Pubblicato da a
Reazioni: 

2 comments:

  1. classical question to test how you play with recursion

    ReplyDelete

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

    ReplyDelete

Subscribe to: Post Comments (Atom)