How to express permutation as the least number of exchanges

The following should give you valid permutations, though I am not sure whether they are always minimal. At least for your second example I get the same number of swaps.

Swaps[orig_, final_] := 
 Rule @@@ (Sequence@@Partition[#,2,1]& /@ First@FindPermutation[final, orig])

Swaps[{a, b, c, 1, 2, 3, 4, 5}, {3, 4, 5, 1, 2, a, b, c}]

{1->6,2->7,3->8}

Swaps[{a, b, c, 1, 2, 3, 4, 5}, {1, 2, 3, 4, a, 5, b, c}]

{1->4,4->7,7->2,2->5,3->6,6->8}

Swaps[{a, b, c, 1, 2, 3, 4, 5}, {3, 4, 5, 2, a, 1, b, c}]

{1->6,6->4,4->5,2->7,3->8}

There is some undocumented functionality you can use for the purpose:

exchanges[v1_, v2_] := Select[MapIndexed[First[#2] -> #1 &, 
                                         LinearAlgebra`LAPACK`PermutationToPivot[
                                         InversePermutation[PermutationList[
                                         FindPermutation[v1, v2]]]]], Apply[Unequal]]

For instance,

exchanges[{a, b, c, 1, 2, 3, 4, 5}, {3, 4, 5, 1, 2, a, b, c}]
   {1 -> 6, 2 -> 7, 3 -> 8}

exchanges[{a, b, c, 1, 2, 3, 4, 5}, {1, 2, 3, 4, a, 5, b, c}]
   {1 -> 4, 2 -> 5, 3 -> 6, 4 -> 7, 5 -> 7, 6 -> 8}