Given two positive integers n and k, print all increasing sequences of length k such that the elements in every sequence are from first n natural numbers.

Examples:

Input: k = 2, n = 3
Output: 1 2
        1 3
        2 3 

Input: k = 5, n = 5
Output: 1 2 3 4 5

Input: k = 3, n = 5
Output: 1 2 3
        1 2 4
        1 2 5
        1 3 4
        1 3 5
        1 4 5
        2 3 4
        2 3 5
        2 4 5
        3 4 5

It’s a good recursion question. The idea is to create an array of length k. The array stores current sequence. For every position in array, we check the previous element and one by one put all elements greater than the previous element. If there is no previous element (first position), we put all numbers from 1 to n.

[ad type=”banner”]

Following is C++ implementation of above idea.

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20%20print%20all%20increasing%20sequences%20of%0A%2F%2F%20length%20’k’%20such%20that%20the%20elements%20in%20every%20sequence%0A%2F%2F%20are%20from%20first%20’n’%20natural%20numbers.%0A%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20contents%20of%20arr%5B0..k-1%5D%0Avoid%20printArr(int%20arr%5B%5D%2C%20int%20k)%0A%7B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Ck%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20arr%5Bi%5D%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20cout%20%3C%3C%20endl%3B%0A%7D%0A%20%0A%2F%2F%20A%20recursive%20function%20to%20print%20all%20increasing%20sequences%0A%2F%2F%20of%20first%20n%20natural%20numbers.%20%20Every%20sequence%20should%20be%0A%2F%2F%20length%20k.%20The%20array%20arr%5B%5D%20is%20used%20to%20store%20current%0A%2F%2F%20sequence.%0Avoid%20printSeqUtil(int%20n%2C%20int%20k%2C%20int%20%26len%2C%20int%20arr%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20If%20length%20of%20current%20increasing%20sequence%20becomes%20k%2C%0A%20%20%20%20%2F%2F%20print%20it%0A%20%20%20%20if%20(len%20%3D%3D%20k)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printArr(arr%2C%20k)%3B%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Decide%20the%20starting%20number%20to%20put%20at%20current%20position%3A%0A%20%20%20%20%2F%2F%20If%20length%20is%200%2C%20then%20there%20are%20no%20previous%20elements%0A%20%20%20%20%2F%2F%20in%20arr%5B%5D.%20%20So%20start%20putting%20new%20numbers%20with%201.%0A%20%20%20%20%2F%2F%20If%20length%20is%20not%200%2C%20then%20start%20from%20value%20of%0A%20%20%20%20%2F%2F%20previous%20element%20plus%201.%0A%20%20%20%20int%20i%20%3D%20(len%20%3D%3D%200)%3F%201%20%3A%20arr%5Blen-1%5D%20%2B%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Increase%20length%0A%20%20%20%20len%2B%2B%3B%0A%20%0A%20%20%20%20%2F%2F%20Put%20all%20numbers%20(which%20are%20greater%20than%20the%20previous%0A%20%20%20%20%2F%2F%20element)%20at%20new%20position.%0A%20%20%20%20while%20(i%3C%3Dn)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20arr%5Blen-1%5D%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20printSeqUtil(n%2C%20k%2C%20len%2C%20arr)%3B%0A%20%20%20%20%20%20%20%20i%2B%2B%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20This%20is%20important.%20The%20variable%20’len’%20is%20shared%20among%0A%20%20%20%20%2F%2F%20all%20function%20calls%20in%20recursion%20tree.%20Its%20value%20must%20be%0A%20%20%20%20%2F%2F%20brought%20back%20before%20next%20iteration%20of%20while%20loop%0A%20%20%20%20len–%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20prints%20all%20increasing%20sequences%20of%0A%2F%2F%20first%20n%20natural%20numbers.%20The%20length%20of%20every%20sequence%0A%2F%2F%20must%20be%20k.%20%20This%20function%20mainly%20uses%20printSeqUtil()%0Avoid%20printSeq(int%20n%2C%20int%20k)%0A%7B%0A%20%20%20%20int%20arr%5Bk%5D%3B%20%20%2F%2F%20An%20array%20to%20store%20individual%20sequences%0A%20%20%20%20int%20len%20%3D%200%3B%20%2F%2F%20Initial%20length%20of%20current%20sequence%0A%20%20%20%20printSeqUtil(n%2C%20k%2C%20len%2C%20arr)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20int%20k%20%3D%203%2C%20n%20%3D%207%3B%0A%20%20%20%20printSeq(n%2C%20k)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]

Output:

1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 3 4
1 3 5
1 3 6
1 3 7
1 4 5
1 4 6
1 4 7
1 5 6
1 5 7
1 6 7
2 3 4
2 3 5
2 3 6
2 3 7
2 4 5
2 4 6
2 4 7
2 5 6
2 5 7
2 6 7
3 4 5
3 4 6
3 4 7
3 5 6
3 5 7
3 6 7
4 5 6
4 5 7
4 6 7
5 6 7
[ad type=”banner”]

Categorized in: