We first focus on the creation of simple permutations before we discuss the creation of equivalent simple permutations. If a permutation n = n(0) has a long cycle, Hannenhalli and Pevzner [5] transform it into a new permutation n(1) by /'breaking" this cycle into two smaller ones. This step is repeated until a simple permutation n(k) is achieved.

On the reality-desire diagram the /'breaking of a cycle" can be described as follows. Let b = (vbi,vb2) be a reality edge and g = (vgi,vg2) a desire edge belonging to a cycle C =(..., vbi,vb2,.vgi,vg2,...) in RD(n(i)). A (b, g)-split of RD(n(i)) produces a new diagram RD(n) = RD(n(i + 1)) which is obtained from RD(n(i)) by:

1. removing edges b and g,

2. adding two new vertices x and y,

3. adding two new reality edges (vbi, x) and (y, vb2),

4. adding two new desire edges (vg1 ,x) and (y,vg2).

Two examples of such splits are illustrated in Fig. 2. As a result of the split the cycles (..., vbi, x, vgi,...) and (..., vb2, y, vg2,...) are created.

The effect of a (b, g)-split on the permutation can be described as follows. x and y are the nodes of a new element which lies between the consecutive elements previously connected by g. That is, we now consider generalized permutations which consists of arbitrary distinct reals instead of permutations of integers. Hannenhalli and Pevzner called the effects of a (b, g)-split on the permutation a (b, g)-padding. We will only use the term (b, g)-split as the two concepts are equivalent.

A (b, g)-split is safe if b and g are non-incident, and n(i) and n(i +1) have the same number of hurdles; i.e. h(n(i)) = h(n(i + 1)). The first condition assures that we do not produce a 1-cycle and a cycle with the same size as the old cycle. Because a split is acting on a long cycle, the first condition is easy to achieve. The second condition assures that the reversal distances of n(i) and n(i + 1) are equal (note that a split increases both n and c by one, and the fortress indicator cannot be changed without changing the number of hurdles). The following lemma shows that to fulfill the second condition, it is sufficient to ensure that the resulting cycles belong to the same component.

Lemma 1 ([5]). Let a (b, g)-split break a cycle C in RD(n(i)) into cycles Ci and C2 in RD(n(i + 1)). Then C is oriented if and only if Ci or C2 is oriented.

In other words, if we do not split a component into two components, the orientation of the component is not changed. For the constructive proof of the existence of safe splits we need the following lemma.

Lemma 2 ([5]). For every desire edge g that does not belong to a 1-cycle, there exists a desire edge f interleaving with g in RD(n). If C is a cycle in RD(n) and f ^ C then f interleaves with an even number of desire edges in C.

Vi V2 V3 V4 V7 Vg Vß V5 V10 V9 Vi V2 V3 X y V4 V7 Vg Vß V5 V10 V9

Vi V2 V3 V4 V7 Vg Vß V5 V10 V9 Vi V2 V3 X y V4 V7 Vg Vß V5 V10 V9

Fig. 2. (a) An unsafe (b, g)-split with b = (v3,v4) and g = (i>i,i>io) that produces a new hurdle. (b) A safe (b,g)-split with b = (v5,v6) and g = (12,13), that does not produce any new components.

Fig. 2. (a) An unsafe (b, g)-split with b = (v3,v4) and g = (i>i,i>io) that produces a new hurdle. (b) A safe (b,g)-split with b = (v5,v6) and g = (12,13), that does not produce any new components.

And for the linear time algorithm we need the following corollary.

Corollary 1. Let C be a cycle of length £ > 1 in RD(n) with desire edges gi to gi. If these desire edges are pairwise non-interleaving, then there exists a gj with 1 < j < £ and a cycle C' = C with a desire edge f, such that f interleaves both gj and gi.

Proof. As C has no pairwise interleaving desire edges, (gi does not interleave with another desire edge of C. So Lemma 2 implies that g£ interleaves with a desire edge f of another cycle C'. Because f is not in C, it interleaves with an even number of desire edges in C .It follows that f interleaves with at least one more desire edge gj (1 < j < £) of C.

Theorem 1 ([5]). If C = (... ,vi,. .. ...) is a long cycle in RD(n), then there exists a safe (b, g)-split acting on C.

The proof given in [5] is constructive. However, the construction cannot transform the whole permutation into a simple permutation in linear time (which is the goal of our paper). Therefore, in Section 5, we provide an algorithm that achieves this goal in linear time.

Was this article helpful?

## Post a comment