# Iterate unique sets of integers

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.

• 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.
– plop
Oct 3, 2020 at 20:30
• @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. Oct 3, 2020 at 20:42
• @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? Oct 3, 2020 at 20:52
• Do you have a set of distinct integers? Oct 3, 2020 at 21:31
• (Depending on context, you can ignore the mechanics.) (Your edit killed a more verbose introduction.) Oct 3, 2020 at 21:57

## 1 Answer

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

• 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! Oct 3, 2020 at 22:02
• Sorry I made a mistake in the code; I'll corrected right now. Oct 3, 2020 at 22:25
• @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. Oct 3, 2020 at 22:32
• yeah that works now. Many thanks Oct 3, 2020 at 23:00
• 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 Oct 3, 2020 at 23:28