# Algorithm for a list of best solutions to the Assignment problem

I am trying to brute force a classical substitution cipher. The problem is that there are $26!$ possible keys. So, I'd like to do frequency analysis to try likely keys first. Then, on the first $n$ tries I will use a dictionary to see if there are actual words in the decryption. That way, I don't need to try all possible keys.

So, as suggested here, I will use chi-squared testing. I was thinking of making a matrix, best illustrated with an example. Suppose in an alphabet {A,B,C} the letter frequencies are 50%, 30% and 20% respectively, and that in a ciphertext the frequencies are 10%, 50% and 40% respectively. Then the A-B cell in the matrix is $(0.1-0.3)^2=0.04$, which is the error rate when a B in plain is encrypted as an A.

   |  A   |  B   |  C                 | Use in plaintext | in ciphertext
---+------+------+------           ---+------------------+---------------
A | 0.16 | 0.04 | 0.01             A |        0.5       |       0.1
B | 0.00 | 0.04 | 0.09             B |        0.3       |       0.5
C | 0.01 | 0.01 | 0.04             C |        0.2       |       0.4


The Hungarian algorithm then gives me a frequency-analysis-wise optimal key: $A \mapsto C, B \mapsto A, C \mapsto B$. This is because the sum of the errors (0.01+0.00+0.01=0.02) is minimal. This is useful, but what I need is the $n$ best keys.

The only thing I can come up with is to run the Hungarian algorithm, and then set one of the cells in the matrix above corresponding to the key found to a high value, so that if you run the algorithm again the key you find doesn't contain the mapping. So, in the example above, you could set A-C to 1 so that when you run the Hungarian algorithm again you find a different key that doesn't contain $A\mapsto C$.

However, this isn't guaranteed to find good keys in order. What would be a better way to extend the Hungarian algorithm to find the best $n$ keys?

Epilogue: after implementing this using D.W.'s approach below, it turned out that this method doesn't perform well enough to crack small-length (at least up to 1000 letters) cipher texts, because frequency analysis alone isn't enough. Performance may be improved by taking frequent digrams or trigrams into account, but I doubt this method can be as powerful as simple hill climbing.

• 1. If you'd like to know about better methods to crack classical substitution ciphers, I encourage you to ask a new question. There are some very cool techniques out there, but they utilize very different methods. 2. The question about how to enumerate the top-$n$ solutions to the assignment problem is still interesting in its own right. I'm trying to figure out if there's a way to reduce it to the problem of finding the $n$ shortest paths in a suitable graph, but I can't quite figure out how to make this idea work.
– D.W.
Jan 4, 2016 at 20:48

Here's one technique to enumerate the best $n$ assignments, for any instance of the assignment problem. I suspect my approach isn't optimal, but it does run in polynomial time: it uses $O(nm)$ invocations of the Hungarian algorithm, where $m$ denotes the number of agents in the problem instance. In your example, $m=26$, so my approach requires $O(n)$ invocations of the Hungarian algorithm.

Let $A_1,A_2,A_3,\dots$ denote the assignments, from best to worse. $A_1$ is the best assignment; $A_2$ is the next-best; and so on. Our goal want to enumerate $A_1,\dots,A_n$.

You can find $A_1$ by solving the original assignment problem, e.g., with the Hungarian algorithm.

How can we find $A_2$, the second-best assignment? The idea is to use a case analysis. Let $v_1,\dots,v_m$ denote the $m$ agents in the problem instance, and let $A(v)$ denote the task assigned to agent $v$ by assignment $A$. We'll break down the space $\mathcal{S}$ of possible candidates for $A_2$ (i.e., the space of all assignments other than $A_1$) into the disjoint union $\mathcal{S} = \mathcal{S}_1 \cup \dots \cup \mathcal{S}_m$, where $\mathcal{S}_i$ is the space of assignments that agree with $A_1$ for $v_1,\dots,v_{i-1}$ but disagree with $A_1$ on $v_i$. (In other words, we look at the first agent that receives a different assignment in $A_1$ vs $A_2$. Then there are $m$ possibilities for that agent; we let $i$ denote its index, i.e., the index of the first agent whose assignment in $A_1$ is different from its assignment in $A_2$. This breaks down the space $\mathcal{S}$ into subspaces $\mathcal{S}_1,\dots, \mathcal{S}_m$, as listed before.)

Now the approach will be to find the best assignment in each $\mathcal{S}_i$, separately.

• $\mathcal{S}_1$: We find the best assignment $A$ such that $A(v_1) \ne A_1(v_1)$ using one invocation of the Hungarian algorithm, by changing the cost of the edge $(v_1,A_1(v_1))$ to $\infty$ (or some very large positive number) and then re-running the Hungarian algorithm. This finds the best assignment out of all assignments that assign $v_1$ to something different than $A_1$ did.

• $\mathcal{S}_2$: We find the best assignment $A$ such that $A(v_1) = A_1(v_1)$ and $A(v_2) \ne A_1(v_2)$ using one invocation of the Hungarian algorithm: change the cost of the edge $(v_1,A_1(v_1))$ to $0$, and change the cost of the edge $(v_2,A_1(v_2))$ to $\infty$.

• $\mathcal{S}_i$: Similarly, for each $i$, we can find the best assignment $A$ such that $A(v_j) = A_1(v_j)$ for all $j=1,2,\dots,i-1$ and such that $A(v_i) \ne A_1(v_i)$, using one invocation of the Hungarian algorithm.

This gives us $m$ assignments, i.e., $m$ candidates for $A_2$. By construction, each one of these assignments is different from $A_1$. Also, by construction, this covers all the space of all assignments that are different from $A_1$. Therefore, $A_2$ will be the best of these $m$ candidates, so we can just compare these $m$ candidates and call it $A_2$.

That find the second-best assignment. How can we find $A_3$, the third-best assignment? Well, the same ideas apply: we'll use a case split, but now the case-split will be a little more involved. Suppose that $v_i$ is the first agent where $A_1$ and $A_2$ disagree (i.e., $A_1$ and $A_2$ agree on $v_1,\dots,v_{i-1}$ but disagree on $v_i$, so that $A_2 \in \mathcal{S}_i$). Then we can break down the space of possibilities for $A_3$ by looking at the first agent that receives a different assignment from $A_2$, or from $A_1$.

In particular, let $\mathcal{T}$ denote the space of possible candidates for $A_3$ (i.e., the space of all assignments other than $A_1$ or $A_2$). We can partition it into the disjoint union

$$\mathcal{T} = \mathcal{S}_1 \cup \dots \cup \mathcal{S}_{i-1} \cup (\mathcal{T}_1 \cup \dots \cup \mathcal{T}_m) \cup \mathcal{S}_{i+1} \cup \dots \cup \mathcal{S}_m.$$

In other words, since $A_2 \in S_i$ and we now want to exclude $A_2$ from the space of allowable assignments, we partition $S_i$ into $S_i = \{A_2\} \cup \mathcal{T}_1 \cup \dots \cup \mathcal{T}_m$ and remove $A_2$. Here $\mathcal{T}_j$ denotes the set of assignments that agree with $A_2$ on $v_1,\dots,v_{j-1}$ but disagrees with $A_2$ on $v_j$ (and, if $j=i$, disagrees with $A_1$ on $v_j$ as well).

Now, we use the Hungarian algorithm to find the best assignment in each of $\mathcal{S}_1, \dots, \mathcal{S}_{i-1}, \mathcal{T}_1, \dots, \mathcal{T}_m, \mathcal{S}_{i+1}, \dots, \mathcal{S}_m$. This is doable using the techniques shown above, using one invocation of the Hungarian algorithm per subspace. Finally, we let $A_3$ be best of all the solutions found.

We can continue in this way, at each step identifying the next-best by decomposing the space of remaining assignments into multiple subspaces and invoking the Hungarian algorithm on each subspace. At each step, we introduce at most $m$ new subspaces, and we can reuse the previously-obtained results for the other subspaces. Therefore, on each step we make at most $m$ invocations of the Hungarian algorithm, so the total number of invocations of the Hungarian algorithm is $O(nm)$.

There's probably a better way to do it, but if you can't find any other algorithm, this is one you could use. Note that this is a general technique for problem of enumerating the $n$ best assignments to any instance of the assignment problem. It's not specific to your substitution-cipher example.

• Here, why do we need to assume that some of the matched edges (in the best assignment) remain intact in the new nodes that you create ? Instead, can we not approach like this : Only discard each existing matched edge from the best assignment one at a time and then compute the best assignment in the modified setting. This gives a set of candidates for the next best assignment. Among this set, as usual the assignment having the minimium cost would be the desired result, i.e. the next best assignment. Thank you. May 21 at 13:40
• @akhil, that sounds like it would work, too. I think both approaches work.
– D.W.
May 21 at 20:38