Finding interesting anagrams

Say that $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$ are two strings of the same length. An anagramming of two strings is a bijective mapping $p:[1\ldots n]\to[1\ldots n]$ such that $a_i = b_{p(i)}$ for each $i$.

There might be more than one anagramming for the same pair of strings. For example, If $a=$abcab and $b=$cabab we have $p_1[1,2,3,4,5]\to[4,5,1,2,3]$ and $p_2[1,2,3,4,5] \to [2,5,1,4,3]$, among others.

We'll say that the weight $w(p)$ of an anagramming $p$ is the number of cuts one must make in the first string to get chunks that can be rearranged to obtain the second string. Formally, this the number of values of $i\in[1\ldots n-1]$ for which $p(i)+1\ne p(i+1)$. That is, it is the number of points at which $p$ does not increase by exactly 1.For example, $w(p_1) = 1$ and $w(p_2) = 4$, because $p_1$ cuts 12345 once, into the chunks 123 and 45, and $p_2$ cuts 12345 four times, into five chunks.

Suppose there exists an anagramming for two strings $a$ and $b$. Then at least one anagramming must have least weight. Let's say this this one is lightest. (There might be multiple lightest anagrammings; I don't care because I am interested only in the weights.)

Question

I want an algorithm which, given two strings for which an anagramming exists, efficiently yields the exact weight of the lightest anagramming of the two strings. It is all right if the algorithm also yields a lightest anagramming, but it need not.

It is a fairly simple matter to generate all anagrammings and weigh them, but there may be many, so I would prefer a method that finds light anagrammings directly.

Motivation

The reason this problem is of interest is as follows. It is very easy to make the computer search the dictionary and find anagrams, pairs of words that contain exactly the same letters. But many of the anagrams produced are uninteresting. For instance, the longest examples to be found in Webster's Second International Dictionary are:

cholecystoduodenostomy
duodenocholecystostomy

The problem should be clear: these are uninteresting because they admit a very light anagramming that simply exchanges the cholecysto, duedeno, and stomy sections, for a weight of 2. On the other hand, this much shorter example is much more surprising and interesting:

coastline
sectional

Here the lightest anagramming has weight 8.

I have a program that uses this method to locate interesting anagrams, namely those for which all anagrammings are of high weight. But it does this by generating and weighing all possible anagrammings, which is slow.

• Just out of curiosity, how do you find pairs of anagrams? Do you do a brute-force $\mathcal O(n^2)$ search within all words of the same length? Jun 7 '12 at 20:54
• No, of course not. You convert each word to a canonical form which has the same letters in alphabetical order. (For example, the canonical form of cholecystoduodenostomy is ccddeehlmnooooossttuyy.) Two words are anagrams if and only if they have the same canonical form. You store the words in a hash table, keyed by their canonical forms, and whenever you find a collision, you have an anagram. Jun 7 '12 at 20:57
• I now have a large amount of more or less related information about this on my blog: (α) (β) (γ) (δ) Sep 13 '17 at 19:50

This problem is known as the “minimum common string partition problem.” (More precisely, the answer in the minimum common string partition problem equals the answer in your problem plus 1.) Unfortunately, it is NP-hard, even with the restriction that each letter occurs at most twice in each of the input strings, as is proved by Goldstein, Kilman, and Zheng [GKZ05]. This means that no polynomial-time algorithm exists unless P=NP. (Of course, if each letter occurs at most once, then the problem is trivial because there is only one anagramming.)

On the positive side, the same authors [GKZ05] give a polynomial-time 1.1037-approximation algorithm under the same restriction. (A “1.1037-approximation algorithm” means an algorithm which may not output the correct answer A but is guaranteed to output a value B such that AB ≤ 1.1037A.) They also give a linear-time 4-approximation algorithm under the weaker restriction that each letter occurs at most three times in each of the input strings.

[GKZ05] Avraham Goldstein, Petr Kolman, and Jie Zheng. Minimum common string partition problem: Hardness and approximations. Electronic Journal of Combinatorics, 12, article R50, 2005. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50

• Jun 12 '12 at 20:38

This is a followup to Tsuyoshi Ito's answer above, summarizing the most relevant portion of the GKZ05 paper he cited.

The paper proves a reduction to the Maximal Independent Set (MIS) problem. Construct a graph $G$ whose vertices are pairs $(i, j)$ such that $a_i = b_j$ and $a_{i+1} = b_{j+1}$. Connect vertices $(i, j)$ and $(k, \ell)$ (where $i≤k$) with an edge whenever it is impossible that an anagramming could map all of $i\mapsto j$ and $i+1\mapsto j+1$ and $k\mapsto\ell$ and $k+1\mapsto\ell+1$. This is easy to detect; such a mapping is impossible exactly if one of the following holds:

1. $i=k$ and $j\ne\ell$
2. $i+1=k$ and $j+1\ne\ell$
3. $i+1<k$ and $\{j, j+1\}$ is disjoint from $\{\ell, \ell+1\}$

Say the resulting graph $G$ has a maximal independent set of size $s$. Then the minimum anagramming weight is exactly $n-s-1$, where $n$ is the length of the strings $a$ and $b$. (The converse holds also: a low-weight anagramming translates directly into a large MIS for $G$. For details, see pp. 4–5 of the paper.)

For example, consider the two strings yttrious and touristy. The corresponding graph has two vertices, one for the shared ou pair and one for the shared ri pair. There is no edge between the vertices, because it is possible to have an anagramming that maps both ou to ou and ri to ri; or one can check that the three conditions above all fail. So the graph obviously has a MIS of size $s=2$ and the minimum anagramming weight is indeed 8-2-1=5, corresponding to the anagramming y|t|t|ri|ou|st|ou|ri|s|t|y.'

On the other hand, consider derater and treader. This time the graph has three vertices:

2 and 3 are incompatible, and 1 and 3 are incompatible, but 1 and 2 are compatible. So the unique MIS has size $s=2$ and contains vertices 1 and 2. The corresponding anagramming of weight 7-2-1=4 is der|a|t|e|rt|r|e|a|der.

• Thank you for the follow-up post, but this is not a proof of NP-completeness of your problem. To prove the NP-completeness of your problem, you have to reduce some known NP-complete problem to your problem, and that is Theorem 2.2 of [GKZ05]. What you presented here (Lemma 1.1 of [GKZ05]) is a reduction in the opposite direction. Jun 13 '12 at 14:24
• This is a nice reformulation. A trivial change that's a minor simplification conceptually (at least for me): instead of drawing edges between pairs that are incompatible and asking for the maximum independent set, we can draw edges between pairs that are compatible, and ask for the maximum clique. (I find it easier to think about "what's the maximum number of pairs that we can keep together".) Feb 22 '17 at 4:48

It doesn't cover the exact algorithm you had in mind (which Tsuyoshi Ito's answer does), but trying to get at the underlying problem of finding "interesting" anagrams...

My first thought was to use some variation on edit-distance, where the atomic changes are weighted according to their "interestingness" rather than the usual "difficulty" or "confusability" weightings. Of course, it seems unlikely that you can efficiently encode the really interesting transformations in this way, since they're likely to be non-local and hence run into the NP-complete issues of MIS, etc.

So, second thought would be to construct a letter-to-letter alignment between the words (à la machine translation alignments), and then to score the alignments themselves for "interestingness" (e.g., counting the alignments that take adjacent letters to non-adjacent letters, or how many alignments each alignment crosses, etc; and then combine them all via loglinear model or such).

Third idea is to completely abandon looking at the structure of the anagramming itself, and instead look at the semantics of the words. Often what makes an anagram "interesting" is the incongruity between the meanings of the words involved. So try something like computing their distance in WordNet, or similar.

The problem can be phrased in terms of permutation groups.

Now a permutation group contains all the "anagram moves", both primitive (swapping two letters) and composite of sequences of primitive moves. It seems that you are interested in only a subset of the possible permutations. I will attempt to define these.

First, recall the notation for permutations, namely, the so-called cycle notation:

• $()$ means no permutation.
• $(1)$ means 1 is swapped with 1, which is also no permutation.
• $(12)$ means 1 and 2 are swapped.
• $(123)$ means 1 replaces 2 which replaces 3 which replaces 1 (a rotation).
• and so one

These simple 'cycles' are composed to describe more complex permutations.

It seems that the moves you are interested in are (for a word of length $n$):

• swaps of pairs of single characters: these are the swaps such as $(12)$
• swaps of pairs of 2 consecutive characters: these are permutations of the form $(a\ b)(a+1\ b+1)$, where $a>0$ and $b<a+1$ and $b+1\le n$
• ...
• swaps of pairs of n consecutive characters: these are permutations of the form $(a\ b)(a+1\ b+1)\cdots(a+i-1\ b+i-1)$ where $a>0$, $a+i-1\le b$, and $b+i-1\le n$.

These moves form the basis for your algorithm. What you are interested in is finding the smallest sequence of these moves to move from one word to the next.

I don't know any algorithm for computing this, apart from the brute force search, but at least now there is a clearer (I hope) description of what the primitive moves are. (And maybe some group theorist among us can point to an appropriate algorithm.)

• Thanks. Perhaps I'm being pessimistic, but it seems to me that this approach is going to be difficult. I don't think a group-theoretic approach will yield fruit unless we first find out what permutation group is of interest, and that varies depending on the input strings. I think efficient representation of finite groups is an extremely deep and rich problem. But I'd like to be mistaken. Jun 7 '12 at 22:08
• “What you are interested in is finding the smallest sequence of these moves to move from one word to the next.” I do not think that this is correct. For example, if n=4, the swap (1 2) has weight 2, but the swap (2 3) has weight 3. Your way of counting does not distinguish these two. Jun 7 '12 at 22:26
• I answered late at night. I didn't understand the weight measure correctly. In fact, I don't understand it now. I though you wanted to allow moves of blocks of letters, which is why I went to all the trouble of defining these primitives. My answer might provide inspiration, so I'll leave it, even though it is wrong. Jun 8 '12 at 5:18

For cholecystoduodenostomy/duodenocholecystostome, I notice that if you assigned a number to each character describing how much it was moved as a delta, you would have some thing like 7 7's, then 8 -7s, then 6 0's. That is not right because some chars may have been repeated (the second c only moved forward 2, not back 7) etc but still very "run length encodable" because you see the same deltas in a row.

Compare to coastline/sectional, where you see something like (+2)(+5)(+5)(-3)(-1)(+3)....much less "run length encodable".

Perhaps the randomness of the deltas could give you a "score" as to how interesting the anagram is?