# Queues and permutation/combination

I am trying to solve this problem, but my permutation-combination skills are a bit rusty. So thought will ask the question here.

There is an ordered queue of 8 items (items on the top = higher priority) and there are 3 teams capable of working on the items in the queue. Each team can work on 2 items at a time. However, not all teams can work on all item. The top 6 items should be picked up. If the teams' capabilities are as shown in the image, how many ways can the top 6 items be picked up?

In general, is there a generic formula for this? That is, "k" items in a queue, "n" teams, and each team know how to work on "r1" , "r2" .."rn" items in the queue

• You can see this question from a graph theoretical point of view. In particular, take the bipartite graph with left set $\{A, B, C\}$ and right set $\{I, F, D, A, B, E\}$, with a team connected to an item if the team can work on the item. Then a way of picking up the items corresponds exactly to a maximal matching of the graph. – B. Mehta Feb 20 '18 at 19:35
• @B.Mehta - it is also conditional. If Team A picks up Item I, it is removed from list of options available for Team C – ram Feb 20 '18 at 19:40
• Yes, this is why it is a matching. In a matching, we cannot include both $AI$ and $CI$. – B. Mehta Feb 20 '18 at 19:42
• AI? CI ? What do those acronyms mean? – ram Feb 20 '18 at 19:45
• The outcome of team $A$ taking item $I$, or equivalently the edge from $A$ to $I$ in the graph described. – JMoravitz Feb 20 '18 at 19:46

There is an ordered queue of 8 items (items on the top = higher priority) ... The top 6 items should be picked up.

Start by simplifying the problem: delete the 7th and 8th items. (And, looking at the table, the 9th one).

In general, is there a generic formula for this? That is, "k" items in a queue, "n" teams, and each team know how to work on "r1" , "r2" .."rn" items in the queue

That depends on what you mean by "generic formula". Given variables which indicate whether a team can work on an item (e.g. $\alpha_{i,j}$ is $0$ if team $i$ cannot work on item $j$ and $1$ if the team can work on the item) then it's possible to write a formula where each term corresponds to an assignment from items to teams and is $1$ if the assignment meets all the rules and $0$ otherwise. But that's not useful from a practical point of view.

A similar approach is to use generating functions: if we have a variable per item then we can represent the team abilities as sums, their ability to do multiple tasks as powers of those sums, and look for the coefficient of $IFDABE$ in $$(I+A+B)^2 (F+D+A+B+E)^2 (I+F+D+E)^2$$ A correction is required to account for the power generating each pair in both orders: i.e. we really want to represent the first team's ability to do two items as the sum $IA+IB+AB$ rather than $I^2+A^2+B^2+2IA+2IB+2AB$. Again, this is not a very practical approach in the general case, although it might be practical in some highly structured specific cases.

A practical solution to this type of problem is to treat it as an instance of a problem called multiset cover. We have a "universe" which is a multiset (a collection of objects which allows repetition):

• Items I, F, D, A, B, E (once each)
• Teams A, B, C (twice each)

And each assignment corresponds to a subset of that universe:

• Item I, team A
• Item A, team A
• ...
• Item E, team C

Note that this treats the items and teams essentially symmetrically: we can think of them both as resources.

Then the multiset cover problem is to find a subset of the subsets which exactly covers the universe. This can't be done efficiently in general, but a practical heuristic is to pick the resource which has fewest options and to try each of those options in turn. This is a slight generalisation of Knuth's Algorithm X to handle multisets rather than sets. It will be called Algorithm M in the forthcoming fascicle 5c of The Art of Computer Programming (link is to the latest version of the work in progress); Knuth's code is available at https://www-cs-faculty.stanford.edu/~knuth/programs/dlx3.w