1
$\begingroup$

I'm trying to figure out of if there's a way to generate all unique sets of integers of length K, where each member has an upper bound of N, and a lower bound of M, without tracking which sets have already been generated, where the order doesn't matter.

To be clear: I'm not looking for ways to filter duplicates from a pre-computed set of sets.

I'm asking if there is an algorithmic approach to generate the unique combinations of values, without producing duplicate combinations/repetitions along the way that must be tested for and removed.

For example, I wrote this counter, which will generate all sets of length K with members bounded at N, but with duplicates.

JavaScript:

function count(k, n, m = 0) {
    // Create counting columns
    let cols = Array(k).fill(m);
    let rows = [];
    
    while (true) {
        rows.push(cols.slice(0));
                
        for (let j = 0; j < k; ++j) {
            ++cols[j];
            
            if (cols[j] <= n) {
                break;
            } else if (j === k - 1) {
                return rows;
            }
            
            // If no overflow, reset column and increment the next on next loop
            cols[j] = m;
        }
    }
}

Output:

> let k=3, n=5, m=1

> count(k, n, m).join('\n');

"1,1,1
2,1,1
3,1,1
1,2,1
2,2,1
3,2,1
1,3,1
2,3,1
3,3,1
1,1,2
2,1,2
3,1,2
1,2,2
2,2,2
3,2,2
1,3,2
2,3,2
3,3,2
1,1,3
2,1,3
3,1,3
1,2,3
2,2,3
3,2,3
1,3,3
2,3,3
3,3,3"

But, as you can see, that produces 1,2,3 as well as 3,2,1.

An example case: if I'm searching for sums of cubes that equal a cube, I don't need to test 2^3 + 16^3 + 12^3 = 18^3 if I've already checked that 2^3 + 12^3 + 16^3 = 18^3.

So I wouldn't want to generate an equivalent set again after having already tested an alternate order of the same terms.

Many thanks.

$\endgroup$
12
  • $\begingroup$ If I understood correctly it looks like you have a set $\{0,1,\ldots,n\}$ and want to list all combinations of $k$ elements allowing repetitions. See here for example. $\endgroup$ – plop Oct 3 '20 at 20:30
  • $\begingroup$ @plop - Thanks - If I understand you and that page correctly, then no, that's not what I'm looking for. I've updated my answer some more - is that more clear? I apologise, I'm not very familiar with proper terminology. $\endgroup$ – thephpdev Oct 3 '20 at 20:42
  • $\begingroup$ @thephpdev to clarify for {1,2,3,4} as your numbers and choosing k = 3 as the size of the subsets {1,2,2} wouldn't be valid? $\endgroup$ – plshelp Oct 3 '20 at 20:52
  • $\begingroup$ Do you have a set of distinct integers? $\endgroup$ – STanja Oct 3 '20 at 21:31
  • 1
    $\begingroup$ (Depending on context, you can ignore the mechanics.) (Your edit killed a more verbose introduction.) $\endgroup$ – greybeard Oct 3 '20 at 21:57
2
$\begingroup$

There is a trick to achieve this. Basically you always keep the subset you are currently considering sorted.

subset = [];
function forSubsets(n,k,m=1){
  if(subset.length == k) console.log(subset);
  else{
    for(var i = m; i <= n; i++){
      subset.push(i);
      forSubsets(n,k,i);
      subset.pop();
    }
  }
}

As you can see on each recursion one element is added to the subset, which is equal or bigger than all previous elements (since the loop starts from m where m is the previously added element). The order for forSubsets(3,2) would be [1,1]; [1,2]; [1,3]; [2,2]; [2,3]; [3,3]; Of course you have to adapt the implementation to your programming language, but I hope the recursive idea is understandable. yield syntax could also be used to implement this concept in a readable manner (e.g. Python). StackOverflow should be a better place for implementation details. By changing the bounds in the for-loop the you could also draw the subsets from $0,...,n-1$ instead of $1,...,n$.

Just for the sake of completeness: Here is the code for generating subsets without duplicate elements (but no duplicate subsets):

subset = [];
function forSubsets(n,k,m=0){
  if(subset.length == k) console.log(subset);
  else{
    for(var i = m+1; i <= n-k+1+subset.length; i++){
      subset.push(i);
      forSubsets(n,k,i);
      subset.pop();
    }
  }
}
$\endgroup$
8
  • $\begingroup$ I tried this out and got some weird results. I've added some concrete examples into my questions. For n = 5 and k = 3 I get: "1,2,3,4,5; 1,2,3,4,6; 1,2,3,4,7; 1,2,3,5,6; 1,2,3,5,7 ..." If I'm being a silly billy and missing something about your proposed solution, please do tell me! $\endgroup$ – thephpdev Oct 3 '20 at 22:02
  • $\begingroup$ Sorry I made a mistake in the code; I'll corrected right now. $\endgroup$ – plshelp Oct 3 '20 at 22:25
  • $\begingroup$ @thephpdev possible error sources are that you didn't use <= in the loop; you use subset.length == n instead of subset.length == k; you mutate subset; if nothing helps I can send you working C++ or python code. $\endgroup$ – plshelp Oct 3 '20 at 22:32
  • $\begingroup$ yeah that works now. Many thanks $\endgroup$ – thephpdev Oct 3 '20 at 23:00
  • $\begingroup$ Hi - Sorry, I didn't look closely enough at the values. This seems to exclude sets with duplicate elements, as well as duplicate sets - this must be why you asked!. Not too worry though @greybeard posted an approach which does the job. My implementation, to be sure I'm not missing anything: pastebin.com/S3MF7PXY $\endgroup$ – thephpdev Oct 3 '20 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.