wu :: forums
« wu :: forums - subset of size k »

Welcome, Guest. Please Login or Register.
Oct 31st, 2024, 4:18pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: SMQ, william wu, Icarus, Eigenray, ThudnBlunder, Grimbal, towr)
   subset of size k
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: subset of size k  (Read 2349 times)
avatar
Newbie
*





   


Posts: 9
subset of size k  
« on: Apr 24th, 2008, 9:58am »
Quote Quote Modify 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: male
Posts: 2276
Re: subset of size k  
« Reply #1 on: Apr 28th, 2008, 11:18am »
Quote Quote Modify Modify

This may help.
IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 2084
Re: subset of size k  
« Reply #2 on: Apr 28th, 2008, 11:42am »
Quote Quote Modify 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: male
Posts: 319
Re: subset of size k  
« Reply #3 on: Apr 30th, 2008, 11:29am »
Quote Quote Modify 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: male
Posts: 7527
Re: subset of size k  
« Reply #4 on: Apr 30th, 2008, 3:59pm »
Quote Quote Modify 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: male
Posts: 319
Re: subset of size k  
« Reply #5 on: Apr 30th, 2008, 8:24pm »
Quote Quote Modify Modify

Very good, thanks
IP Logged

While we are postponing, life speeds by
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board