Problema della distanza inversa

L’obiettivo di questo problema è quello di effettuare due permutazioni e, trovare le serie di inversioni più breve per trasformare l’una nell’altra. Come input si hanno due permutazioni π e σ e come output, invece, una serie di inversioni ρ₁,…, ρ _t che trasforma π in σ, in modo che t sia la minima. Chiamiamo t la distanza inversa tra π e σ, e d(π, σ) per indicare la distanza di inversione per un dato π e σ. In pratica si è soliti selezionare l’ordine di un secondo genoma come standard ideale, e arbitrariamente stabilire che σ sia l’identity permutation 1,2,……,n.