Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Test run result of ex-3.15
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.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment