{"id":25979,"date":"2017-10-26T09:21:48","date_gmt":"2017-10-26T03:51:48","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25979"},"modified":"2017-10-26T09:21:48","modified_gmt":"2017-10-26T03:51:48","slug":"c-programming-print-possible-combinations-r-elements-given-array-size-n","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-print-possible-combinations-r-elements-given-array-size-n\/","title":{"rendered":"C++ Programming – Print all possible combinations of r elements in a given array of size n"},"content":{"rendered":"

Given an array of size n, generate and print all possible combinations of r elements in array. For example, if input array is {1, 2, 3, 4} and r is 2, then output should be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} and {3, 4}.<\/span><\/p>\n

Following are two methods to do this.<\/p>\n

Method 1 (Fix Elements and Recur)<\/strong>
\nWe create a temporary array \u2018data[]\u2019 which stores all outputs one by one. The idea is to start from first index (index = 0) in data[], one by one fix elements at this index and recur for remaining indexes. Let the input array be {1, 2, 3, 4, 5} and r be 3. We first fix 1 at index 0 in data[], then recur for remaining indexes, then we fix 2 at index 0 and recur. Finally, we fix 3 and recur for remaining indexes. When number of elements in data[] becomes equal to r (size of a combination), we print data[].<\/p>\n

Following diagram shows recursion tree for same input.<\/p>\n

\"Combination\"
\nFollowing is C++ implementation of above approach.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20Program%20to%20print%20all%20combination%20of%20size%20r%20in%20an%20array%20of%20size%20n%0A%23include%20%3Cstdio.h%3E%0Avoid%20combinationUtil(int%20arr%5B%5D%2C%20int%20data%5B%5D%2C%20int%20start%2C%20int%20end%2C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20index%2C%20int%20r)%3B%0A%20%0A%2F%2F%20The%20main%20function%20that%20prints%20all%20combinations%20of%20size%20r%0A%2F%2F%20in%20arr%5B%5D%20of%20size%20n.%20This%20function%20mainly%20uses%20combinationUtil()%0Avoid%20printCombination(int%20arr%5B%5D%2C%20int%20n%2C%20int%20r)%0A%7B%0A%20%20%20%20%2F%2F%20A%20temporary%20array%20to%20store%20all%20combination%20one%20by%20one%0A%20%20%20%20int%20data%5Br%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Print%20all%20combination%20using%20temprary%20array%20\u2019data%5B%5D\u2019%0A%20%20%20%20combinationUtil(arr%2C%20data%2C%200%2C%20n-1%2C%200%2C%20r)%3B%0A%7D%0A%20%0A%2F*%20arr%5B%5D%20%20\u2014%3E%20Input%20Array%0A%20%20%20data%5B%5D%20\u2014%3E%20Temporary%20array%20to%20store%20current%20combination%0A%20%20%20start%20%26%20end%20\u2014%3E%20Staring%20and%20Ending%20indexes%20in%20arr%5B%5D%0A%20%20%20index%20%20\u2014%3E%20Current%20index%20in%20data%5B%5D%0A%20%20%20r%20\u2014%3E%20Size%20of%20a%20combination%20to%20be%20printed%20*%2F%0Avoid%20combinationUtil(int%20arr%5B%5D%2C%20int%20data%5B%5D%2C%20int%20start%2C%20int%20end%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20index%2C%20int%20r)%0A%7B%0A%20%20%20%20%2F%2F%20Current%20combination%20is%20ready%20to%20be%20printed%2C%20print%20it%0A%20%20%20%20if%20(index%20%3D%3D%20r)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20j%3D0%3B%20j%3Cr%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20data%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20printf(%22%5Cn%22)%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%20replace%20index%20with%20all%20possible%20elements.%20The%20condition%0A%20%20%20%20%2F%2F%20%22end-i%2B1%20%3E%3D%20r-index%22%20makes%20sure%20that%20including%20one%20element%0A%20%20%20%20%2F%2F%20at%20index%20will%20make%20a%20combination%20with%20remaining%20elements%0A%20%20%20%20%2F%2F%20at%20remaining%20positions%0A%20%20%20%20for%20(int%20i%3Dstart%3B%20i%3C%3Dend%20%26%26%20end-i%2B1%20%3E%3D%20r-index%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20data%5Bindex%5D%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20combinationUtil(arr%2C%20data%2C%20i%2B1%2C%20end%2C%20index%2B1%2C%20r)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%202%2C%203%2C%204%2C%205%7D%3B%0A%20%20%20%20int%20r%20%3D%203%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20printCombination(arr%2C%20n%2C%20r)%3B%0A%7D\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/strong><\/p>\n

1 2 3\r\n1 2 4\r\n1 2 5\r\n1 3 4\r\n1 3 5\r\n1 4 5\r\n2 3 4\r\n2 3 5\r\n2 4 5\r\n3 4 5<\/pre>\n
How to handle duplicates?<\/em>
\nNote that the above method doesn\u2019t handle duplicates. For example, if input array is {1, 2, 1} and r is 2, then the program prints {1, 2} and {2, 1} as two different combinations. We can avoid duplicates by adding following two additional things to above code.
\n1) Add code to sort the array before calling combinationUtil() in printCombination()
\n2) Add following lines at the end of for loop in combinationUtil()<\/p>\n
        \/\/ Since the elements are sorted, all occurrences of an element\r\n        \/\/ must be together\r\n        while (arr[i] == arr[i+1])\r\n             i++;<\/pre>\n
See this <\/a><\/strong>for an implementation that handles duplicates.<\/p>\n[ad type=\u201dbanner\u201d]\n
Method 2 (Include and Exclude every element)<\/strong>
\nLike the above method, We create a temporary array data[]. The idea here is similar to Subset Sum Problem<\/a>. We one by one consider every element of input array, and recur for two cases:<\/p>\n
1) The element is included in current combination (We put the element in data[] and increment next available index in data[])
\n2) The element is excluded in current combination (We do not put the element and do not change index)<\/p>\n
When number of elements in data[] become equal to r (size of a combination), we print it.<\/p>\n
This method is mainly based on Pascal\u2019s Identity<\/a>, i.e. nc<\/sub>r<\/sub> = n-1c<\/sub>r<\/sub> + n-1c<\/sub>r-1<\/sub><\/strong><\/p>\n
Following is C++ implementation of method 2.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Program%20to%20print%20all%20combination%20of%20size%20r%20in%20an%20array%20of%20size%20n%0A%23include%3Cstdio.h%3E%0Avoid%20combinationUtil(int%20arr%5B%5D%2Cint%20n%2Cint%20r%2Cint%20index%2Cint%20data%5B%5D%2Cint%20i)%3B%0A%20%0A%2F%2F%20The%20main%20function%20that%20prints%20all%20combinations%20of%20size%20r%0A%2F%2F%20in%20arr%5B%5D%20of%20size%20n.%20This%20function%20mainly%20uses%20combinationUtil()%0Avoid%20printCombination(int%20arr%5B%5D%2C%20int%20n%2C%20int%20r)%0A%7B%0A%20%20%20%20%2F%2F%20A%20temporary%20array%20to%20store%20all%20combination%20one%20by%20one%0A%20%20%20%20int%20data%5Br%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Print%20all%20combination%20using%20temprary%20array%20\u2019data%5B%5D\u2019%0A%20%20%20%20combinationUtil(arr%2C%20n%2C%20r%2C%200%2C%20data%2C%200)%3B%0A%7D%0A%20%0A%2F*%20arr%5B%5D%20%20\u2014%3E%20Input%20Array%0A%20%20%20n%20%20%20%20%20%20\u2014%3E%20Size%20of%20input%20array%0A%20%20%20r%20%20%20%20%20%20\u2014%3E%20Size%20of%20a%20combination%20to%20be%20printed%0A%20%20%20index%20%20\u2014%3E%20Current%20index%20in%20data%5B%5D%0A%20%20%20data%5B%5D%20\u2014%3E%20Temporary%20array%20to%20store%20current%20combination%0A%20%20%20i%20%20%20%20%20%20\u2014%3E%20index%20of%20current%20element%20in%20arr%5B%5D%20%20%20%20%20*%2F%0Avoid%20combinationUtil(int%20arr%5B%5D%2C%20int%20n%2C%20int%20r%2C%20int%20index%2C%20int%20data%5B%5D%2C%20int%20i)%0A%7B%0A%20%20%20%20%2F%2F%20Current%20cobination%20is%20ready%2C%20print%20it%0A%20%20%20%20if%20(index%20%3D%3D%20r)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20j%3D0%3B%20j%3Cr%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2Cdata%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20printf(%22%5Cn%22)%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%20When%20no%20more%20elements%20are%20there%20to%20put%20in%20data%5B%5D%0A%20%20%20%20if%20(i%20%3E%3D%20n)%0A%20%20%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20%2F%2F%20current%20is%20included%2C%20put%20next%20at%20next%20location%0A%20%20%20%20data%5Bindex%5D%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20combinationUtil(arr%2C%20n%2C%20r%2C%20index%2B1%2C%20data%2C%20i%2B1)%3B%0A%20%0A%20%20%20%20%2F%2F%20current%20is%20excluded%2C%20replace%20it%20with%20next%20(Note%20that%0A%20%20%20%20%2F%2F%20i%2B1%20is%20passed%2C%20but%20index%20is%20not%20changed)%0A%20%20%20%20combinationUtil(arr%2C%20n%2C%20r%2C%20index%2C%20data%2C%20i%2B1)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%202%2C%203%2C%204%2C%205%7D%3B%0A%20%20%20%20int%20r%20%3D%203%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20printCombination(arr%2C%20n%2C%20r)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/p>\n
1 2 3\r\n1 2 4\r\n1 2 5\r\n1 3 4\r\n1 3 5\r\n1 4 5\r\n2 3 4\r\n2 3 5\r\n2 4 5\r\n3 4 5<\/pre>\n
How to handle duplicates in method 2?<\/em>
\nLike method 1, we can following two things to handle duplicates.
\n1) Add code to sort the array before calling combinationUtil() in printCombination()
\n2) Add following lines between two recursive calls of combinationUtil() in combinationUtil()<\/p>\n
        \/\/ Since the elements are sorted, all occurrences of an element\r\n        \/\/ must be together\r\n        while (arr[i] == arr[i+1])\r\n             i++;<\/pre>\n
See this <\/a><\/strong>for an implementation that handles duplicates.<\/p>\n[ad type=\u201dbanner\u201d]\n
\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"
C++ Programming – Print all possible combinations of r elements in a given array of size n – Mathematical Algorithms – Given an array of size n, and r is 2.<\/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,1,74058],"tags":[73383,74845,76423,76413,76420,76418,74851,76432,76419,76429,70851,76427,74847,73721,75062,72067,72058,70047,76434,70832,76426,70811,70824,76424,76425,76430,76428,70822,74260,76421,75074,70838,76431,76422,76417,70323,70331,70328,73693,70384,70347,76433,76414,70808,74081,76415,70830,76416,70810,70836],"class_list":["post-25979","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","category-mathematical-algorithms","tag-alphabet-pattern-programs-in-c","tag-basic-c-program-examples","tag-basic-c-programs","tag-basic-c-programs-asked-in-interview","tag-basic-c-programs-for-beginners","tag-basic-c-programs-for-interviews","tag-basic-programs-in-c","tag-c-basic-programs","tag-c-code-examples","tag-c-interview-programs","tag-c-language-examples","tag-c-language-programs-examples","tag-c-progra","tag-c-program-for-permutation-of-numbers","tag-c-program-to-count-number-of-words-in-a-string","tag-c-program-to-print-patterns-of-numbers","tag-c-program-to-print-patterns-of-numbers-and-alphabets","tag-c-programming","tag-c-programming-basics","tag-c-programming-codes","tag-c-programming-com","tag-c-programming-examples","tag-c-programming-examples-with-output","tag-c-programming-language-examples","tag-c-programming-programs","tag-c-programs-asked-in-interview","tag-c-programs-for-interview","tag-c-programs-with-output","tag-combination-math","tag-cs-language-code","tag-example-c-program","tag-example-of-c-program","tag-interview-programs-in-c","tag-ncr-in-maths","tag-outcome-possibilities-calculator","tag-permutation-and-combination","tag-permutation-and-combination-formula","tag-permutation-formula","tag-permutation-of-string","tag-permutation-program-in-c","tag-permutations-and-combinations-formula","tag-program-in-c","tag-programming-examples","tag-programming-in-c","tag-programming-interview-questions","tag-sample-c-code","tag-sample-c-program","tag-sample-programs-in-c","tag-simple-c-programs","tag-simple-c-programs-with-output"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25979","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=25979"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25979\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25979"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25979"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25979"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}