Subset of permutations in JavaScript with up to~6 duplicates per element

Question

I have tried to this answer to find all permutations of size K=6 of an array of strings, but the array I'm permuting is way too large (~13,000 elements but I can guarantee most of those will be duplicates), which means I'm getting:

....
re-permuting with 6925/12972
node:internal/console/constructor:257
   value: function(streamSymbol, string) {
                   ^
RangeError: Maximum call stack size exceeded  
    at console.value (node:internal/console/constructor:257:20)  
    at console.log (node:internal/console/constructor:359:26)  
    at permute (/home/path/to/code/permutation.js:22:17)  
    at permute (/home/path/to/code/permutation.js:23:9)  
    .....
re-permuting with 6924/12972
....
re-permuting with 6918/12972

And then it dies. I guessed that is the recursion that's the problem.

I know that there's at most ~300 unique elements in my input (which is how I know that many of the array elements must be duplicates), but I don't know if that's 10,000 instances of one element, and then the rest are individually unique elements or at least K of each unique element. Because of that I can't just fed them into a Set, and there maybe fewer than K of one element so I can't just create a new input by duplicating the new ones K times.

Here is my slightly modified (for readability and logging only) version of the code from the above linked answer (on second look, this algorithm is far from optimal):

let permArr = [];
let usedChars = [];
let originalLength;
/**
 * Subsets of permutations of an array
 * @param {any[]} input array of elements to permute
 * @param {number} subsetLength size of the subsets to return
 * @returns {Array[]} and array of arrays
 */
function permute(input, subsetLength = input.length) {
    let index
    let ch;
    originalLength ??= input.length;
    for (index = 0; index < input.length; index++) {
        ch = input.splice(index, 1)[0];
        usedChars.push(ch);
        if (input.length == 0) {
            let toAdd = usedChars.slice(0, subsetLength);
            // resizing the returned array to size k
            if (!permArr.includes(toAdd)) permArr.push(toAdd);
        }
        console.log(`re-permuting with ${input.length}/${originalLength}`)
        permute(input, subsetLength);
        input.splice(index, 0, ch);
        usedChars.pop();
    }
    return permArr
};

And I found this answer but I do not follow it at all, and this other answer is similar but still uses recursion.

How can I make this without recursion/more performant so it can handle much larger arrays? I'm using NodeJs, and I'm not averse to using different data types.

Answer 1

I don't know if that's 10,000 instances of one element, and then the rest are individually unique elements or at least K of each unique element. Because of that I can't just fed them into a Set, and there maybe fewer than K of one element so I can't just create a new input by duplicating the new ones K times

So just group and count them. Seems simple enough:

function subsetPermutations(arr, size) {
    const counts = {};
    for (const el of arr) {
        counts[el] = (counts[el] ?? 0) + 1;
    }
    const unique = Object.keys(counts);
    const result = Array.from({length: size});
    function* recurse(depth) {
        if (depth == size) {
            yield result;
        } else {
            for (const el of unique) {
                if (counts[el]) {
                    result[depth] = el;
                    counts[el]--;
                    yield* recurse(depth+1)
                    counts[el]++;
                }
            }
        }
    }
    return recurse(0);
}

for (const perm of subsetPermutations(["a", "b", "b", "c", "c", "c"], 3)) {
    console.log(perm.join('-'));
}

I have tried to this answer to find all permutations of size K=6, but the array I'm permuting is way too large (~13,000 elements), however I can guarantee I know that there's at most ~300 unique

That's still roughtly 300⁶ permutations, which is far too many to put them into an array. The function above is designed as an iterator so that you can work on the current result in a loop before it gets mutated in the next iteration, to avoid any allocation overhead, but it still will take too long to generate all of them.

How can I make this without recursion/more performant so it can handle much larger arrays? I'm using NodeJs, and I'm not averse to using different data types.

You can use a Map instead of the object for counts, but I doubt it'll be much faster for just 300 different elements.

Avoiding recursion is unnecessary since it only goes 6 level deep, there won't be a stack overflow unlike with your inefficient solution. But for performance, you might still try this approach of dynamically generating nested loops.