Problema dello spostamento del pancake

Anche prima che i biologi si confrontassero con il problema del riarrangiamento del genoma gli informatici avevano studiato il procedimento relativo al “Sorting by prefix reversal”, conosciuto anche come il problema del mettere in ordine i pancakes:

il problema è il seguente, data una pila di n pancake, qual è il numero minimo di spostamenti per riporli in una pila perfetta?

In input vi sono π permutazioni mentre in output una serie di inversioni prefissate ρ₁, …, ρ_t per trasformare π in una permutazione identica in modo che t sia la minima.

Questo problema è ispirato ad una situazione reale: un cuoco trasandato ha preparato pancakes di diversa grandezza lasciandoli poi in disordine. Il cameriere vuole metterli in ordine in modo tale che il più grande sia alla base e il più piccolo in cima. Può farlo solo facendo saltare in aria i pancakes, cambiandoli di posto tante volte quante è necessario per riordinarli. Volendo utilizzare l’algoritmo di greedy per risolvere il problema dei pancakes allora si avranno 2 inversioni prefissate al massimo per mettere il pancake nella sua giusta posizione, massimo

2n–2 passaggi totali. 

William Gates and Christos Papadimitriou hanno dimostrato a metà degli anni 70 che questo problema poteva essere risolto con al massimo 5/3 (n + 1) inversioni prefissate. Comunque il problema dei pancakes è rimasto irrisolto.

Fig.5 Christos Papadimitrou e William Gates che ordinano i pancake.