Help Me Please: Combination with DP

Moderator: Board moderators

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Help Me Please: Combination with DP

Hi all,
I'm very weak in dynamic programming. I want to know abt how i get all posible combination for a given set by dynamic approach.
Like n=4, {1,2,3,4}
If r=2, then
ncr=6
1,2
1,3
1,4
2,3
2,4
3,4
If r=3 then ncr=4, i can get ncr value by general simple dp. But how can i find all possible combination(like --> {1,2},{1,3},...) by dp if range is n>12 or more. When n<12 then i can got it by backtracking. But its not ok for large n. Please help me. Thanks in advance.

N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
k-subsets of {1, ..., n}
Let the first subset be {1, ..., k}.
Find the next subset after Y = {y_1, ..., y_k} (where y_1 < ... < y_k)
• * find the first i, such that y_i+1 not_in Y
* increase y_i by 1, set y_j = j for j < i, and return the new set Y
* this fails if i=k, y_k = n, in which case Y = {n-k+1, ..., n} is the last such subset
Source: Peter J. Cameron: Combinatorics: Topics, techniques, algorithms

---

If you find something better, let me know

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong
Hi Nino,
Thankx. I'm trying to understand it. Thanks again.

N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
Demonstration:

4-subset of {1, 2, 3, 4, 5, 6}:

1, 2, 3, 4
1+1 is already here, 2+1 is also, ... but 4+1 is not, so:
1, 2, 3, 5
1, 2, 4, 5
1, 3, 4, 5
2, 3, 4, 5
remember if we upgrade the i-th element y_i to y_i+1, we set everything before it to 1, 2, ...
1, 2, 3, 6
1, 2, 4, 6
1, 3, 4, 6
2, 3, 4, 6
again: 4 -> 5 and everything before it becomes 1, 2, 3, 4, ...
1, 2, 5, 6
1, 3, 5, 6
2, 3, 5, 6
1, 4, 5, 6
2, 4, 5, 6
3, 4, 5, 6
Now 6 should be upgraded to 7, which is not available so we're done

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
The STL way: (warning, untested code ahead)

Code: Select all

``````vector<int> A;
int K;