Cheap and Secure Web Hosting Provider : See Now

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

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.