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

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?

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.

• I don't understand why $[a a]$ is allowable when you say that $a$ can appear twice, but it wasn't allowable in the first instance, when there was no limit on the number of times $a$ can appear. Why aren't $[a a], [b b]$ etc. listed in the first example? Jul 10, 2019 at 14:16
• Are there not multiple different sets of combinations which could independent meet the counting criteria? So from all the two combinations you could have either ([a b],[c,d]) or ([a,c],[b,d]) or ([a,d],[b,c]) so in effect you are not longer turning a list in to a set of lists (combinations) , but a list in to a set of sets of lists? Jul 10, 2019 at 14:19
• You are both right. I'm gonna add aa bb... to the explanation, and also add that there are multiple sets that meet the criteria. In fact, the point of the algorithm is to calculate all sets that meet the criteria, not just one. Sorry for the confusion, it's a bit hard for me to wrap my head around this problem. Jul 10, 2019 at 14:34
• Please edit the question to tell us how large your typical input will be. How many letters $n$ in total on the original list? Are the duplicate counts generally a large fraction of $n$, or a small fraction? An efficient algorithm is probably different if you have only three different letters in a list of $100$, or if you have $95$ different letters in a list of $100$. Jul 10, 2019 at 15:58
• Will do, thanks for the reminder. $n$ is always $[0, 9]$, and each letter is picked randomly from a pool of 8 letters. I will also more explicitly point out that for $n >=6$ the algorithm has to return combinations of three pairs, and if it's $n>=8$, combinations of four pairs. Jul 10, 2019 at 16:20

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.

• Hi, thanks for your answer. This works! But for $n=7$ it takes a few seconds, and the time it takes to complete goes longer and longer until $n=9$ in which it takes too long for it to actually be usable in a javascript application. However, it may be that my code isn't efficient in doing what you said. Here it is so you can take a look: pastebin.com/rTg8Hims Note that I use Ramda.js to check if the permutation is already in the array, and js-combinatorics to make the permutations. Jul 10, 2019 at 19:32

Let's say your distinct entries are a 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.

• Thank you for your answer. This algorithm does certainly work for $n<6$, but my application needs to return triples of pairs for $n>=6$ and quartets for $n>=8$, since $n$ is in $[0, 9]$. I edited the post to make that clearer, it was my mistake not doing it earlier. Sorry for the confusion. Jul 10, 2019 at 16:28