1
$\begingroup$

I hope people will indulge me a potentially pretty easy problem.

I have a table like the following: \begin{array}{|c|c|c|c|} \hline & A & B & C \\ \hline D & 70 & 23 & 0\\ \hline E & 80 & 0 & 16 \\ \hline F & 40 & 86 & 0 \\ \hline \end{array}

The columns represent jobs, the rows represent candidates, and the numbers represent the percent match. For example, Candidate D is a 70% fit for Job A and a 23% fit for Job B, but isn't a fit in the least for job C.

The constraint, of course, is that you can only have one candidate per job - i.e. you can only select one item per row and one per column. If you assign Candidate D to job A, you can't also assign that candidate to Job B. Similarly, if you've already filled Job A, you can't assign, for example, Candidate E to it.

Note that this is specifically not limited to a 3x3 table like I show above - the problem is just some mxn table, where m and n may or may not be equal. (Obviously, $m, n \in \mathbb{N}$).

In this case, in the first step, you have $3$ choices. In the second step, you have $2$ choices. In the final step, you only have $1$ choice. This is true regardless of which job or candidate to start with. In this particular case, it just so happens that $3 + 2 + 1 = 3 * 2 * 1 = 3!$. if $n \le m$, there will be $n! = 3! = 3 * 2 * 1 = 6$ possible arrangements. This just happens to be true for a 3x3 table, though, so, in general it won't be the case that $n! = n + (n - 1) + (n - 2) + ... + 1$.

Am I correct in thinking that, if $n \le m$, this is just $$\frac{m!}{(m-n)!}$$

Or do I have to go with $$n + (n - 1) + (n - 2) + ... + 1$$ after all? (I was confusing myself horribly earlier and even tried $$n * (n + (n - 1) + (n - 2) + ... + 1)$$ at one point, but I don't think that that's correct).

For context (and this isn't what I'm asking about at this point), my ultimate goal is to come up with a way to identify which assignment of candidates to jobs will result the greatest satisfaction all around. In the case of the table I showed above, you should assign candidate D to job A, candidate E to job C, and candidate F to job B for a total "satisfaction rating" of $70 + 16 + 86 = 172$. For the sake of comparison, I'm trying to figure out the difficulty of a "brute force" algorithm - that kind of a solution would be fine for a small table like this, but if you had hundreds of jobs and candidates I'll probably want to be a little smarter than that.

$\endgroup$
  • 1
    $\begingroup$ This is weighted bipartite matching. See the Hungarian method. $\endgroup$ – saulspatz Jul 19 '18 at 23:51
  • $\begingroup$ It's not clear what your question is. The title seems to indicate that you want to know the number of possible selections; the text near the end rather suggests that you want an algorithm for optimizing over all selections. $\endgroup$ – joriki Jul 20 '18 at 5:19
  • $\begingroup$ @joriki No, I'm just looking for an answer to the question in the title. The last paragraph is just context. $\endgroup$ – EJoshuaS Jul 20 '18 at 12:48
  • $\begingroup$ @saulspatz Thanks, that's a very constructive piece of information - it could be very valuable. $\endgroup$ – EJoshuaS Jul 20 '18 at 16:07
2
$\begingroup$

You're right that the number of different selection for $m\ge n$ is

$$ \frac{m!}{(m-n)!}\;. $$

There are $m$ possible selections in the first column, $m-1$ in the second, and so on, until the $n$-th column, where there are $m-n+1$ selections left. These are all independent and thus need to be multiplied, leading to your result.

$\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.