Help Me Please: Combination with DP

Let's talk about algorithms!

Moderator: Board moderators

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

Help Me Please: Combination with DP

Post by Chok » Tue Oct 11, 2005 6:42 pm

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.

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

Post by N|N0 » Thu Oct 20, 2005 3:42 pm

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

Post by Chok » Thu Oct 20, 2005 3:50 pm

Hi Nino,
Thankx. I'm trying to understand it. Thanks again.

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

Post by N|N0 » Thu Oct 20, 2005 6:40 pm

Demonstration:

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

We start with:
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 :D

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Thu Oct 20, 2005 11:33 pm

The STL way: (warning, untested code ahead)

Code: Select all

vector<int> A;
int K;
load_data(A,K);
int N = A.size();
vector<int> selected(N,0);
for (int i=N-1; i>=N-K; i--) selected[i]=1;
do {
  for (int i=0; i<N; i++) if (selected[i]) cout << a[i] << " "; cout << endl;
} while (next_permutation(selected.begin(),selected.end()));

Post Reply

Return to “Algorithms”