Step by Step solution about How to resolve the algorithm Topswops step by step in the Python programming language

The code defines a function called f1 that takes a permutation (a list of numbers) as input and returns the number of swaps required to sort it. The function works by iterating over the permutation, starting from the first element, and repeatedly reversing the sublist up to the current element if the current element is not equal to 1. The number of swaps is incremented each time a sublist is reversed.

The code then defines a function called fannkuch that takes a number n as input and returns the maximum number of swaps required to sort any permutation of length n. The function does this by calling the f1 function for each permutation of length n and returning the maximum number of swaps.

The code then prints the maximum number of swaps required to sort permutations of length 1 to 10.

The second half of the code is an optimized version of the fannkuch function called topswops. This function uses a bitmask to keep track of which elements have been sorted and a loop to try all possible swaps. The function returns the minimum number of swaps required to sort any permutation of length n.

The code then prints the minimum number of swaps required to sort permutations of length 1 to 12.

>>> from itertools import permutations
>>> def f1(p):
	i = 0
	while True:
		p0  = p[0]
		if p0 == 1: break
		p[:p0] = p[:p0][::-1]
		i  += 1
	return i

>>> def fannkuch(n):
	return max(f1(list(p)) for p in permutations(range(1, n+1)))

>>> for n in range(1, 11): print(n,fannkuch(n))

1 0
2 1
3 2
4 4
5 7
6 10
7 16
8 22
9 30
10 38
>>>


try:
    import psyco
    psyco.full()
except ImportError:
    pass

best = [0] * 16

def try_swaps(deck, f, s, d, n):
    if d > best[n]:
        best[n] = d

    i = 0
    k = 1 << s
    while s:
        k >>= 1
        s -= 1
        if deck[s] == -1 or deck[s] == s:
            break
        i |= k
        if (i & f) == i and d + best[s] <= best[n]:
            return d
    s += 1

    deck2 = list(deck)
    k = 1
    for i2 in xrange(1, s):
        k <<= 1
        if deck2[i2] == -1:
            if f & k: continue
        elif deck2[i2] != i2:
            continue

        deck[i2] = i2
        deck2[:i2 + 1] = reversed(deck[:i2 + 1])
        try_swaps(deck2, f | k, s, 1 + d, n)

def topswops(n):
    best[n] = 0
    deck0 = [-1] * 16
    deck0[0] = 0
    try_swaps(deck0, 1, n, 0, n)
    return best[n]

for i in xrange(1, 13):
    print "%2d: %d" % (i, topswops(i))