[Solved]: Find all non-decreasing sequences given lenght and size

Problem Detail: 

I'm trying to find a solution for this exercise:

Give the pseudocode of an algorithm which takes two positive integers n and k and prints all the non-decreasing sequences of length k (1,2,...,n).

For example n=4, k=3:

111 112 113 114 122 123 124 133 134 144 222 223 224 233 234 244 333 334 344 444

the complexity must be O(n S(n,k)) with S(n,k) the number of the sequences to print for n and k.

i think from the complexity required that a backtracking algorithm it's needed but i could'nt solve it.

i tried something like this:

P(n,k,h: prefix length, S: sequence)        if h == k then            OUTPUT S       else          for i=1 to n do              if(i>=S[h])                     S[h+1]=i;                    P(n,k,h+1,S); 

Asked By : Maikos

Answered By : David Richerby

Hint. Given the available time complexity, a simple recursive algorithm should work. If you need a sequence of length $k$ from the set $\{m, \dots, n\}$ you either include $m$ or you don't.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21664

 Ask a Question

 Download Related Notes/Documents