Iterate unique sets of integers

Question

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.

Answer 1

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();
    }
  }
}