{"id":26956,"date":"2018-01-05T21:07:36","date_gmt":"2018-01-05T15:37:36","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26956"},"modified":"2018-01-05T21:07:36","modified_gmt":"2018-01-05T15:37:36","slug":"c-programming-print-increasing-sequences-length-k-first-n-natural-numbers","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-print-increasing-sequences-length-k-first-n-natural-numbers\/","title":{"rendered":"C++ Programming &#8211; Print all increasing sequences of length k from first n natural numbers"},"content":{"rendered":"<p>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.<span id=\"more-131805\"><\/span><\/p>\n<p>Examples:<\/p>\n<pre>Input: k = 2, n = 3\r\nOutput: 1 2\r\n        1 3\r\n        2 3 \r\n\r\nInput: k = 5, n = 5\r\nOutput: 1 2 3 4 5\r\n\r\nInput: k = 3, n = 5\r\nOutput: 1 2 3\r\n        1 2 4\r\n        1 2 5\r\n        1 3 4\r\n        1 3 5\r\n        1 4 5\r\n        2 3 4\r\n        2 3 5\r\n        2 4 5\r\n        3 4 5<\/pre>\n<p>It\u2019s 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.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Following is C++ implementation of above idea.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20%20print%20all%20increasing%20sequences%20of%0A%2F%2F%20length%20\u2019k\u2019%20such%20that%20the%20elements%20in%20every%20sequence%0A%2F%2F%20are%20from%20first%20\u2019n\u2019%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\u2019len\u2019%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\u2013%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\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>1 2 3\r\n1 2 4\r\n1 2 5\r\n1 2 6\r\n1 2 7\r\n1 3 4\r\n1 3 5\r\n1 3 6\r\n1 3 7\r\n1 4 5\r\n1 4 6\r\n1 4 7\r\n1 5 6\r\n1 5 7\r\n1 6 7\r\n2 3 4\r\n2 3 5\r\n2 3 6\r\n2 3 7\r\n2 4 5\r\n2 4 6\r\n2 4 7\r\n2 5 6\r\n2 5 7\r\n2 6 7\r\n3 4 5\r\n3 4 6\r\n3 4 7\r\n3 5 6\r\n3 5 7\r\n3 6 7\r\n4 5 6\r\n4 5 7\r\n4 6 7\r\n5 6 7<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>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.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515],"tags":[77853,80404,80412,80401,77858,80411,80403,80402,70483,71496,80413,72994,77860,80398,72839,80409,80400,80408,78228,80399,77870,80407,77851,80405],"class_list":["post-26956","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","tag-best-book-on-dynamic-programming","tag-best-dp","tag-change-dp","tag-coding-tutorials","tag-different-dp","tag-dp-best","tag-dp-nice","tag-dp-star","tag-dynamic-programming","tag-dynamic-programming-algorithm","tag-dynamic-programming-ebook","tag-dynamic-programming-in-python","tag-dynamic-tutorial","tag-example-of-dynamic","tag-how-to-solve-dynamic-programming-problems","tag-program-program","tag-programing-simplified","tag-programming-basics","tag-programming-problems","tag-programming-simplified","tag-programming-tutorial","tag-programming-tutorials","tag-what-is-dp","tag-whats-up-dp"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26956","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26956"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26956\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26956"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26956"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26956"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}