Author |
Topic: subset of size k (Read 2349 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
|
|
|
|