sort_sequences.py

# sort_sequences.py
# Callum Howard, 2017

from itertools import permutations, combinations

def compswap(swap, inputs):
    if (inputs[swap[0]] > inputs[swap[1]]):
        inputs[swap[0]], inputs[swap[1]] = inputs[swap[1]], inputs[swap[0]]
    return inputs

def verify(swaps, size, verbose=False):
    for perm in permutations(range(size)):
        perm = list(perm)
        copy = list(perm)
        for swap in swaps:
            copy = compswap(swap, copy)
        if not copy == range(size):
            #print 'failed with {} on {}, result was {}'.format(swaps, perm, copy)
            return False
        if verbose:
            print '\tpassed with {} on {}, result was {}'.format(swaps, perm, copy)
    return True

def gen_swaps(n_swaps, size):
   return permutations(combinations(range(size), 2), n_swaps)

def num_swaps(n_swaps, size):
   return sum(1 for _ in gen_swaps(n_swaps, size))

def find_swap_sequence(n_swaps, size):
    for swaps in gen_swaps(n_swaps, size):
        if verify(swaps, size):
            verify(swaps, size, False)
            print 'verified', swaps, 'by exhaustion'
            return
    print 'no swap sequence with', n_swaps, 'swaps for', size, 'items found'

#print num_swaps(8, 5)
#print num_swaps(10, 6)
find_swap_sequence(3, 3)

#swaps = [(0, 1), (0, 2), (1, 2)]
#swaps = [(0, 1), (2, 3), (0, 2), (1, 3), (1, 2)]
#swaps = [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (3, 4), (1, 3), (2, 4), (2, 3)]