™
Mou Code
Divacon Trace Output
monosort-- source --
randarr = shuffled(4)
nest = PDC(d_lr,c_lr, !(min,max) @ #!corr, id, atom, id)
monosort = PDC(d_lr,c_lr, id, !nest @ !(min,max) @ #!mirr, atom, id)
trace(monosort, randarr)
-- end source --
-- lib: monosort_lib.py --
"""Helpers for monosort.dc.
Loaded via: ./pydc dcsrc/monosort.dc dcsrc/monosort_lib.py
`randints(N)` returns 2^N random integers in [0, 99] — small enough that
the trace stays readable, big enough that collisions are rare for small N.
`shuffled(N)` returns a uniform permutation of [0..2^N - 1] — useful for
verifying the sort end-to-end (output should be [0, 1, ..., 2^N - 1])."""
import random
def randints(N, lo=0, hi=99, seed=None):
"""List of 2**N random integers in [lo, hi]."""
if seed is not None:
random.seed(seed)
return [random.randint(lo, hi) for _ in range(2 ** N)]
def shuffled(N, seed=None):
"""A random permutation of [0..2**N - 1]."""
if seed is not None:
random.seed(seed)
arr = list(range(2 ** N))
random.shuffle(arr)
return arr
-- end lib --
-- trace: monosort([11,0,3,9,4,15,13,2,1,12,5,14,10,8,7,6]) --
monosort([11,0,3,9,4,15,13,2,1,12,5,14,10,8,7,6])
divide d_lr -> ([11,0,3,9,4,15,13,2], [1,12,5,14,10,8,7,6])
monosort([11,0,3,9,4,15,13,2])
divide d_lr -> ([11,0,3,9], [4,15,13,2])
monosort([11,0,3,9])
divide d_lr -> ([11,0], [3,9])
monosort([11,0])
divide d_lr -> ([11], [0])
monosort([11])
⇣ atom; basef -> [11]
monosort([0])
⇣ atom; basef -> [0]
post #!mirr -> ([(11, 0)], [(0, 11)])
post !(min, max) -> ([0], [11])
post !nest -> ([0], [11])
combine c_lr -> [0,11]
monosort([3,9])
divide d_lr -> ([3], [9])
monosort([3])
⇣ atom; basef -> [3]
monosort([9])
⇣ atom; basef -> [9]
post #!mirr -> ([(3, 9)], [(9, 3)])
post !(min, max) -> ([3], [9])
post !nest -> ([3], [9])
combine c_lr -> [3,9]
post #!mirr -> ([(0, 9),(11, 3)], [(3, 11),(9, 0)])
post !(min, max) -> ([0,3], [11,9])
post !nest -> ([0,3], [9,11])
combine c_lr -> [0,3,9,11]
monosort([4,15,13,2])
divide d_lr -> ([4,15], [13,2])
monosort([4,15])
divide d_lr -> ([4], [15])
monosort([4])
⇣ atom; basef -> [4]
monosort([15])
⇣ atom; basef -> [15]
post #!mirr -> ([(4, 15)], [(15, 4)])
post !(min, max) -> ([4], [15])
post !nest -> ([4], [15])
combine c_lr -> [4,15]
monosort([13,2])
divide d_lr -> ([13], [2])
monosort([13])
⇣ atom; basef -> [13]
monosort([2])
⇣ atom; basef -> [2]
post #!mirr -> ([(13, 2)], [(2, 13)])
post !(min, max) -> ([2], [13])
post !nest -> ([2], [13])
combine c_lr -> [2,13]
post #!mirr -> ([(4, 13),(15, 2)], [(2, 15),(13, 4)])
post !(min, max) -> ([4,2], [15,13])
post !nest -> ([2,4], [13,15])
combine c_lr -> [2,4,13,15]
post #!mirr -> ([(0, 15),(3, 13),(9, 4),(11, 2)], [(2, 11),(4, 9),(13, 3),(15, 0)])
post !(min, max) -> ([0,3,4,2], [11,9,13,15])
post !nest -> ([0,2,3,4], [9,11,13,15])
combine c_lr -> [0,2,3,4,9,11,13,15]
monosort([1,12,5,14,10,8,7,6])
divide d_lr -> ([1,12,5,14], [10,8,7,6])
monosort([1,12,5,14])
divide d_lr -> ([1,12], [5,14])
monosort([1,12])
divide d_lr -> ([1], [12])
monosort([1])
⇣ atom; basef -> [1]
monosort([12])
⇣ atom; basef -> [12]
post #!mirr -> ([(1, 12)], [(12, 1)])
post !(min, max) -> ([1], [12])
post !nest -> ([1], [12])
combine c_lr -> [1,12]
monosort([5,14])
divide d_lr -> ([5], [14])
monosort([5])
⇣ atom; basef -> [5]
monosort([14])
⇣ atom; basef -> [14]
post #!mirr -> ([(5, 14)], [(14, 5)])
post !(min, max) -> ([5], [14])
post !nest -> ([5], [14])
combine c_lr -> [5,14]
post #!mirr -> ([(1, 14),(12, 5)], [(5, 12),(14, 1)])
post !(min, max) -> ([1,5], [12,14])
post !nest -> ([1,5], [12,14])
combine c_lr -> [1,5,12,14]
monosort([10,8,7,6])
divide d_lr -> ([10,8], [7,6])
monosort([10,8])
divide d_lr -> ([10], [8])
monosort([10])
⇣ atom; basef -> [10]
monosort([8])
⇣ atom; basef -> [8]
post #!mirr -> ([(10, 8)], [(8, 10)])
post !(min, max) -> ([8], [10])
post !nest -> ([8], [10])
combine c_lr -> [8,10]
monosort([7,6])
divide d_lr -> ([7], [6])
monosort([7])
⇣ atom; basef -> [7]
monosort([6])
⇣ atom; basef -> [6]
post #!mirr -> ([(7, 6)], [(6, 7)])
post !(min, max) -> ([6], [7])
post !nest -> ([6], [7])
combine c_lr -> [6,7]
post #!mirr -> ([(8, 7),(10, 6)], [(6, 10),(7, 8)])
post !(min, max) -> ([7,6], [10,8])
post !nest -> ([6,7], [8,10])
combine c_lr -> [6,7,8,10]
post #!mirr -> ([(1, 10),(5, 8),(12, 7),(14, 6)], [(6, 14),(7, 12),(8, 5),(10, 1)])
post !(min, max) -> ([1,5,7,6], [14,12,8,10])
post !nest -> ([1,5,6,7], [8,10,12,14])
combine c_lr -> [1,5,6,7,8,10,12,14]
post #!mirr -> ([(0, 14),(2, 12),(3, 10),(4, 8),(9, 7),(11, 6),(13, 5),(15, 1)], [(1, 15),(5, 13),(6, 11),(7, 9),(8, 4),(10, 3),(12, 2),(14, 0)])
post !(min, max) -> ([0,2,3,4,7,6,5,1], [15,13,11,9,8,10,12,14])
post !nest -> ([0,1,2,3,4,5,6,7], [8,9,10,11,12,13,14,15])
combine c_lr -> [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
-- result: [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
--
|