Author |
Topic: subset of size k (Read 2346 times) |
|
avatar
Newbie
Posts: 9
|
 |
subset of size k
« on: Apr 24th, 2008, 9:58am » |
 Quote  Modify
|
Input an integer array of size n and an integer k (k<=n), output all subsets of size k.
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
|
Re: subset of size k
« Reply #1 on: Apr 28th, 2008, 11:18am » |
Quote Modify
|
This may help.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: subset of size k
« Reply #2 on: Apr 28th, 2008, 11:42am » |
Quote Modify
|
If I understand the question right, I'd do something like this:
void printAllSubsets(int* arr, unsigned int n, unsigned int k) {
// sanity check
if (k == 0 || k > n) return;
// current subset is given by array of indexes
unsigned int idx = new unsigned int[k];
for(int i = 0; i < k; i++) idx[i] = i;
// loop through all subsets
for( ; ; ) {
// print current subset
for(int i = 0; i < k; i++) cout << (i > 0 ? "," : "") << arr[idx[i]];
cout << endl;
// check for termination
if (idx[0] == n - k) break;
// advance to next subset
for(int i = 0; i < k; i++) {
// if idx[i] has room to increment
if (i + 1 == k || idx[i] + 1 < idx[i+1]) {
// increment index and stop here
idx[i]++;
break;
} else {
// otherwise reset index
idx[i] = i;
}
}
}
// clean up
delete[] idx;
}
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: subset of size k
« Reply #3 on: Apr 30th, 2008, 11:29am » |
Quote Modify
|
ugh SMQ plesae elaborate a bit more on the implementation, I don't understand why you need idx.
thx
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: subset of size k
« Reply #4 on: Apr 30th, 2008, 3:59pm » |
Quote Modify
|
For example, with 3 items among 5, it generates the following subsets:
xxx--
xx-x-
x-xx-
-xxx-
xx--x
x-x-x
-xx-x
x--xx
-x-xx
--xxx
As you can see, the first x that can move right is moved right, and those to the left of that one are reset to the left margin.
The indexes contain the position of each x. It is the position of an element to include in the subset. The inner loop search for an index that can be incremented and resets all indexes on the way to the minimum value.
|
|
IP Logged |
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: subset of size k
« Reply #5 on: Apr 30th, 2008, 8:24pm » |
Quote Modify
|
Very good, thanks
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print