×

# generating all combinations of size r from n elements?

 0 Can anyone tell me an efficient method and implementation of how to generate all combinations of size r from a given array of n elements? asked 22 Jul '15, 18:18 3★sandeep9 478●2●8●27 accept rate: 4% Are all elements distinct ? (22 Jul '15, 19:12)

 0 Use recursion (backtracking). For selecting 'r' elements from a set of size 'n', we can either select first element and then select 'r-1' elements from the rest of 'n-1' elements or we do not select first element and choose 'r' elements from the remaining 'n-1' elements. This is the combinatorial proof of the formula C(n,r) = C(n-1,r-1) + C(n-1,r) This is also an induction formula, and as you can see, size of sub problem decreases at each step. We can write a function which uses this algorithm to determine all the combinations of 'r' elements from a set of 'n' elements. C++ Code : Ideone Link answered 25 Jul '15, 16:57 221●3●4 accept rate: 27%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×69

question asked: 22 Jul '15, 18:18

question was seen: 3,215 times

last updated: 25 Jul '15, 16:57