Permutations in the array: the minimum number of pairwise permutations to get from one array to another and is it possible

To find out how many pairwise exchanges (swaps) of letters are needed to turn one input string into another, when letters can be repeated, you can find all possible permutations of the indices that make another from one string ( get_permutations() ), and then calculate for each resulting permutations of the number of exchanges that it requires using the number_of_swaps(permutation) function , and select a minimum number of exchanges:

 #!/usr/bin/env python import itertools from collections import Counter, defaultdict def get_permutations(a, b): """Generate all permutations that convert *a* sequence into *b* sequence.""" positions = defaultdict(list) # letter -> "list of positions in *a*" for position, letter in enumerate(a): positions[letter].append(position) # generate all permutations choosing all available indices at each position #NOTE: using product() is not very efficient here but it is simple multiset = (positions[letter] for letter in b) for permutation in itertools.product(*multiset): if len(permutation) == len(set(permutation)): yield permutation 

This function expects that you can turn a string into b , that is, any of the following has been executed:

 # assert that we can permute *a* string into *b* assert len(a) == len(b) and all(a.count(c) == b.count(c) for c in set(a)) assert Counter(a) == Counter(b) assert sorted(a) == sorted(b) # each of the 3 assertions is enough by itself 

get_permutations(a, b) returns lists of indices (permutations) such that a turns into b :

 # assert that *permutation* permutes *a* into *b* assert [a[p] for p in permutation] == list(b) # each of the 2 is enough by itself assert all(c == a[permutation[i]] for i, c in enumerate(b)) 

Each call to get_permutations() generates m[c1]! * m[c2]! ... m[c1]! * m[c2]! ... m[c1]! * m[c2]! ... permutation, where m[ci] (multiplicity) is the number of times the letter ci repeated in the input word, eh ! this is factorial. For example, for TTAGGG line 2! * 1! * 3! == 12 2! * 1! * 3! == 12 2! * 1! * 3! == 12 permutations are generated.

To find the minimum number of pairwise exchanges:

 def minimal_number_of_swaps(a, b): """Find the minimal number of swaps to convert *a* into *b* sequence.""" return min(map(number_of_swaps, get_permutations(a, b))) 

Example:

 assert list(get_permutations('kamal', 'amalk')) == [(1,2,3,4,0), (3,2,1,4,0)] assert minimal_number_of_swaps('kamal', 'amalk') == 3 

Here, (1,2,3,4,0) permutation requires 4 pairwise exchanges to get (0,1,2,3,4) (single permutation), and (3,2,1,4,0) permutation requires only 3 :

 (3,2,1,4,0) -> # меняем 0,3 пару индексов (0,2,1,4,3) -> # меняем 1,2 пару индексов (0,1,2,4,3) -> # меняем 3,4 пару индексов (0,1,2,3,4) 

The same permutation, but in the form of letters:

 01234 01243 02143 32140 kamal -> kamla -> kmala -> amalk 

still:

 yoda_words = "in the force strong you are".split() normal_words = "you are strong in the force".split() assert minimal_number_of_swaps(normal_words, yoda_words) == 5 

here the letters are whole words, and since all words are unique, one could use a simpler get_permutation() function, since only one permutation is possible. number_of_swaps(permutation) works by counting how many cycles are present in the permutation — the result is equal to len(permutation) - ncycles .