0
$\begingroup$

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?enter image description here

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – B. Mehta Feb 20 '18 at 19:35
  • $\begingroup$ @B.Mehta - it is also conditional. If Team A picks up Item I, it is removed from list of options available for Team C $\endgroup$ – ram Feb 20 '18 at 19:40
  • $\begingroup$ Yes, this is why it is a matching. In a matching, we cannot include both $AI$ and $CI$. $\endgroup$ – B. Mehta Feb 20 '18 at 19:42
  • $\begingroup$ AI? CI ? What do those acronyms mean? $\endgroup$ – ram Feb 20 '18 at 19:45
  • $\begingroup$ The outcome of team $A$ taking item $I$, or equivalently the edge from $A$ to $I$ in the graph described. $\endgroup$ – JMoravitz Feb 20 '18 at 19:46
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.