Combinations with constraint: each element can only appear up to X times.

Question

I'm trying to develop a JavaScript app that needs a certain algorithm to work, but I have not been able to figure it out.I believe the task I have to perform is better explained with an example:

Let's say I have a list of letters:

$\begin{bmatrix}a & b & c & d\end{bmatrix}$

Note that, in my application, the number of letters $n$, is always in $[0, 9]$, and that each letter is picked randomly from a pool of 8 letters.

From there, I can get all 2-combinations (with repetition) of the list:

$\begin{bmatrix}a & b\end{bmatrix}$ $\begin{bmatrix}a & c\end{bmatrix}$ $\begin{bmatrix}a & d\end{bmatrix}$ $\begin{bmatrix}b & c\end{bmatrix}$ $\begin{bmatrix}b & d\end{bmatrix}$ $\begin{bmatrix}c & d\end{bmatrix}$ $\begin{bmatrix}a & a\end{bmatrix}$ $\begin{bmatrix}b & b\end{bmatrix}$ $\begin{bmatrix}c & c\end{bmatrix}$ $\begin{bmatrix}d & d\end{bmatrix}$

Now I want to get all 2-combinations from this list of combinations, but with one constraint: each letter can only be used up to a number of times, and this number can change. Let's say for example, we set that all letters can only appear once, so you could make:

$\begin{bmatrix}a & b\end{bmatrix}$ and $\begin{bmatrix}c & d\end{bmatrix}$

But not:

$\begin{bmatrix}a & b\end{bmatrix}$ and $\begin{bmatrix}a & c\end{bmatrix}$

Because $a$ appears in both elements.

Also note that in this example $n=4$, so you can at most pick two pairs of items. But if $n$ is greater, the algorithm should return three pairs of letters in each combination for $n>=6$ and four pairs for $n>=8$.

But let's say we now set that $a$ can appear up to two times, and $ b c d$ can only appear once each. So now, the combination $\begin{bmatrix}a & b\end{bmatrix}$ and $\begin{bmatrix}a & c\end{bmatrix}$ would be valid, and also the combination $\begin{bmatrix}a & a\end{bmatrix}$ and $\begin{bmatrix}b & c\end{bmatrix}$, but not $\begin{bmatrix}a & a\end{bmatrix}$ and $\begin{bmatrix}b & b\end{bmatrix}$ because $b$ can only appear once.

As you can see, there are multiple sets of combinations that meet the criteria, and in fact the point of the algorithm is to calculate ALL sets that meet the criteria, not just one.

I also noticed that when you have an odd number of letters, there will be one leftover letter in each set of combinations. I also need the algorithm to tell me which letter was leftover in each set of combinations, but I believe this won't be a problem because you can substract the combinations from the original list.

The only way I've managed to do this is to calculate all possible combinations, then filter out the ones that don't comply with the constraints, but this seems very inefficient and looks like there has to be a better way to do it. Any ideas?

Thanks in advance.

EDIT: I'm sorry for all the important information that I unknowingly omitted.I'm adding it as soon as I see someone requesting it. In case it helps anyone, my application is in fact not about letters, but about Teamfight Tactics (a videogame) items. If anyone is familiar with the game, that should help them better understand my question. I didn't want to say it initially because I thought I should only talk about the mathematics here, but I now see it could help clarify the problem.

Answer 1

Based on this comment:

$n$ is always $[0,9]$, and each letter is picked randomly from a pool of $8$ letters.

I don't think you need an efficient algorithm. because $9! = 362880$ is really a pretty small number for a computer. So you can afford to look at them all and filter out repetitions.

There are well known algorithms that generate the permutations of $n$, either one at a time or in a list. So pcik your $n$ letters, allowing for repetitions, and loop on the permutations.

Start with an empty list of the sets you are looking for.

Loop on the permutations.

Suppose you see $$ dcaabadb . $$ Think of that as the candidate $$ [dc][aa][ba][db] $$ Now sort each pair and then sort the pairs by their smallest first element to get $$ [aa][ab][bd][cd] $$ Check to see whether that's already on your list and add it if it's not.

(You need only look at the permutation $aaabbdcd$. If you maintain the list cleverly in alphabetical order that will be a quick search and addition.)

When you've looked at all the permutations you will have all the sets of pairs you want.

Edit in response to comment.

The code relies on built in functions and structures (as it should) so I can't see how to optimize it without digging in to implementations. But there are several strategies that might make enough difference.

If $n$ is even then all the letters will have to be used, so you can put the lexicographically smallest one first and just permute the rest. That reduces the time for $n=8$ to that for $n=7$ (and speeds up $n=4$ and $6$)

Dealing with $n=9$ looks a little trickier..

If $n$ is odd and at least one letter is duplicated (which must happen when $n=9$) then you will have to use at least one of the duplicates so think of that one as lexicographically first, start with it and permute the rest. That reduces $n=9$ to $n=8$. (But you can't then use the previous trick to get down to $n=7$.)

If you can detect when your permutation generator gives you $ba$ relative to where $ab...$ appears you can skip it. That will cut the time in half most of the time.

You might be able to find more tinkering improvements like these with some data. Run the algorithm (even though it's slow) and count how many acceptable lists of pairs you actually get for various repetition patterns in the input data. How does that number compare to the number of permutations.

Answer 2

Let's say your distinct entries are a[1] to a[n].

Here's a simple algorithm to iterate over all possible combinations:

for i = 1 to n: for j = 1 to n: for k = 1 to n: for l = 1 to n:
    if is_valid_pair_of_pairs( (a[i],a[j]), (a[k],a[l]) ):
        do_something_with( (a[i],a[j]), (a[k],a[l]) )

This will do the trick, but using this method, pairs of pairs may be considered up to eight times each. To avoid that problem, you can change your iteration boundaries:

for i = 1 to n: for j = i to n: for k = i to n: for l = k to n:
    if is_valid_pair_of_pairs( (a[i],a[j]), (a[k],a[l]) ):
        do_something_with( (a[i],a[j]), (a[k],a[l]) )

Note that both j and k begin at i, and l begins at k. This is not a typo.

With this, you'll check each unique pair of pairs exactly once, but you'll still need is_valid_pair_of_pairs to check that if the same index occurs multiple times it is really allowed to do so.