Test run result of ex-3.15

gistfile1.txt

n = 0
n = 1
1 initial orders were sortable within 0 ops.
n = 2
1 initial orders were sortable within 0 ops.
2 initial orders were sortable within 1 ops.
n = 3
1 initial orders were sortable within 0 ops.
4 initial orders were sortable within 1 ops.
6 initial orders were sortable within 2 ops.
n = 4
1 initial orders were sortable within 0 ops.
7 initial orders were sortable within 1 ops.
18 initial orders were sortable within 2 ops.
24 initial orders were sortable within 3 ops.
n = 5
1 initial orders were sortable within 0 ops.
11 initial orders were sortable within 1 ops.
46 initial orders were sortable within 2 ops.
96 initial orders were sortable within 3 ops.
120 initial orders were sortable within 4 ops.
n = 6
1 initial orders were sortable within 0 ops.
16 initial orders were sortable within 1 ops.
101 initial orders were sortable within 2 ops.
326 initial orders were sortable within 3 ops.
600 initial orders were sortable within 4 ops.
720 initial orders were sortable within 5 ops.

gistfile2.txt

from itertools import *
import copy



#print "n = ", n, ", initial orders = ", ini_orders

def check(n):
    print "n = %d" % n
    l0 = range(n)
    ini_orders = list(permutations(l0))
    for k in range(n):
        count = 0
        for l in ini_orders:
            l = list(l)
            j = sortable_within(l0, l, k)
            if j > 0:
                count += 1
                # print "%s sortable within %d steps" % (l, k)
        print "%d initial orders were sortable within %d ops." % (count, k)

def sortable_within(l0, l, k):
    count = 0
    ipairs = list(combinations(l0, 2))
    # if l == [2, 0, 1]:
    #     print "ipairs = ", ipairs
    for j in range(k + 1):
        perm_chains = list(combinations(ipairs, j))
        # if l == [2, 0, 1]:
        #     print "checking chain length %d, perm_chains = %s" % (j, perm_chains)
        for perms in perm_chains:
            l1 = copy.deepcopy(l)
            for perm in perms:
                if perm:
 #                   print "perm =", perm
                    l1 = compare_and_swap(l1, perm)
                    # if l == [2, 0, 1]:
                    #     print "l1 = %s" % l1
            if l1 == l0:
                count += 1
                return count
    return count

def compare_and_swap(l, perm):
    (i, j) = perm
    if l[i] > l[j]:
        tmp = l[i]
        l[i] = l[j]
        l[j] = tmp
    return l

if __name__ == '__main__':
    for n in range(6 + 1):
        check(n)