2
$\begingroup$

Suppose I have distinct letters in an alphabet $\sum = \{a_1,a_2,...,a_n\}$. I also have two permutations of these letters, let's call them $A,B$. How can I find the Edit distance between $A$ and $B$ with block edit operations allowed?

To make it clearer, an example would be $\sum =\{a,b,c,d \}$. Two possible permutations are $A=``abcd",B=``dabc"$. The edit distance here would be $1$ because we can swap the block $``abc"$ with $``d"$ to get one string to the other.

Clearly, there won't be any deletions/insertions in this form of the problem, it will purely be swaps since the two strings are permutations of the same letters.

Now I know that the original edit-block problem with all operations is NP-Hard, however, would the restriction of only block swaps perhaps make this solvable in polynomial time? Most text I've read don't address this version and instead address variations of the original problem. Any help would be appreciated.

Improve this question
$\endgroup$
5
  • $\begingroup$ @YuvalFilmus Sorry for the confusion, I guess the entire first paragraph can be summarized as: $A$ is a permutation of $B$ and the letters in $A$ are distinct. I tried being too formal to avoid confusion but that just led to more confusion. $\endgroup$
    – AspiringMat
    Commented Feb 5, 2017 at 13:15
  • 1
    $\begingroup$ Cross-posted on cstheory.se: cstheory.stackexchange.com/questions/37471/…. $\endgroup$
    – Yuval Filmus
    Commented Feb 5, 2017 at 15:15
  • 2
    $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W. ♦
    Commented Feb 5, 2017 at 15:45
  • $\begingroup$ This is from the meta: "If you were asking the question on SE sites with different topics, then you should adapt the question to better suit the site where the question is being asked. In the case where the same question is on-topic in both the sites as it is". I haven't copy pasted the question from one site to the other, I adapted the question on one site to suit its background. I don't really think this is cross site posting but rather trying to access the problem from different angles. $\endgroup$
    – AspiringMat
    Commented Feb 5, 2017 at 23:05
  • $\begingroup$ @user3508551, where are you quoting from? The definitive post is here: meta.stackexchange.com/q/64068/160917, and it says "Is cross-posting permitted?" "NO". (And I don't see much adaptation; it's the same problem and same question.) $\endgroup$
    – D.W. ♦
    Commented Feb 6, 2017 at 4:27

2 Answers 2

Reset to default
5
$\begingroup$

When one operation is exactly "removing a block and inserting it between two other positions", the problem of computing the string distance is known as Transposition Distance. It is NP-hard even if both input sequences are $p$-sequences, that is, if every letter occurs only once in each input sequence:

Laurent Bulteau, Guillaume Fertin, Irena Rusu: Sorting by Transpositions Is Difficult. SIAM J. Discrete Math. 26(3): 1148-1180 (2012)

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ By the way, turns out it is possible to do in polynomial time (Since this is a special case). The authors of the paper you linked to cited another paper which can perform this in $O(n^2)$ if one word is a permutation of the other, which is exactly my case. $\endgroup$
    – AspiringMat
    Commented Feb 9, 2017 at 7:48
  • $\begingroup$ @C Komus:The abstract of that paper says it looks at transposing two consecutive blocks, which is not the same as taking a block out and arbitrarily reinserting it somewhere. $\endgroup$
    – reinierpost
    Commented Feb 9, 2017 at 8:29
  • $\begingroup$ Transposing two consecutive blocks is exactly the same as cutting out one block and reinserting it at an arbitrary position: Let $uvwx$ be a string where $u$, $v$, $w$, and $x$ are substrings. Cutting out $w$ and inserting it between $u$ and $v$ is the same as transposing $v$ and $w$. I misunderstood the question, however, as it should also be allowed to swap nonconsecutive blocks, for example to transform $uvwx$ into $xvwu$ in one operation. Maybe the example in the question could be changed to reflect that. $\endgroup$
    – Christian Komusiewicz
    Commented Feb 9, 2017 at 9:04
1
$\begingroup$

Thanks to C Komus for providing the initial paper. After reading in the paper that he added, the authors cited another paper which can perform it if the words are permutations of each others, which is exactly my case. I found that this is indeed possible in polynomial time. $O(n^2)$ to be exact.

David A. Christie: Sorting permutations by block interchanges. Information Processing Letters, 1996, 60, 4, 165-169

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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