Page 1 of 1
Help Me Please: Combination with DP
Posted: Tue Oct 11, 2005 6:42 pm
by Chok
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.
Posted: Thu Oct 20, 2005 3:42 pm
by N|N0
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
Posted: Thu Oct 20, 2005 3:50 pm
by Chok
Hi Nino,
Thankx. I'm trying to understand it. Thanks again.
Posted: Thu Oct 20, 2005 6:40 pm
by N|N0
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
Posted: Thu Oct 20, 2005 11:33 pm
by misof
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()));