Am primit o singură soluţie crorectă ,de la Aurel Ionescu:
Suma minima este de 10 euro, evident in cazurile in care aranjarea initiala nu este identica cu cea finala (atunci ar fi 0 euro) sau daca se poate face cu o singura permutare, sau cu un numar de permutari disjuncte (5 euro) de exemplu
10 9 8 7 6 5 4 3 2 1 in 1 2 3 4 5 6 7 8 9 10
(10,1), (9,2), (8,3), (7,4), (6,5)
Conform teoriei , orice permutare poate fi reprezentata ca o compozitie de cicluri disjuncte, iar fiecare ciclu poate fi rezolvat în două etape.
Un ciclu este o functie π : {v1,v2,…vn}->{v1,v2,…vn} care mapeaza
v1-> v2 -> … -> vk-1 -> vk -> v1
Luam exemplul din problemă
10 6 8 5 2 3 1 4 7 9
si sa presupunem ca vrem sa ajungem la
1 2 3 4 5 6 7 8 9 10.
Un ciclu este 10 --> 9 --> 7 --> 1 --> 10.
Al doilea ciclu este 6 --> 3 --> 8 --> 4 --> 5 --> 2 --> 6.
Primul ciclu presupune două etape: primul pas: (10,1), (9,7) si al doilea pas: (10,7) Al doilea ciclu implică, două etape: primul pas: (6,2), (3,5), (8,4) si al doilea pas: (6,5), (3,4).
Facem pașii în paralel:
Primul pas: (10,1), (9,7), (6,2), (3,5), (8,4)
Al doilea pas: (10,7), (6,5), (3,4).
10 6 8 5 2 3 1 4 7 9 initial
1 2 4 3 6 5 10 8 9 7 cerem in prima comanda
1 2 3 4 5 6 7 8 9 10 final