1ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao"""Utilities for enumeration of finite and countably infinite sets. 2ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao""" 3ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao### 4ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao# Countable iteration 5ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 6ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao# Simplifies some calculations 7ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaoclass Aleph0(int): 8ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao _singleton = None 9ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao def __new__(type): 10ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if type._singleton is None: 11ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao type._singleton = int.__new__(type) 12ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return type._singleton 13ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao def __repr__(self): return '<aleph0>' 14ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao def __str__(self): return 'inf' 15ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 16ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao def __cmp__(self, b): 17ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return 1 18ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 19ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao def __sub__(self, b): 20ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao raise ValueError,"Cannot subtract aleph0" 21ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao __rsub__ = __sub__ 22ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 23ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao def __add__(self, b): 24ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return self 25ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao __radd__ = __add__ 26ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 27ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao def __mul__(self, b): 28ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if b == 0: return b 29ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return self 30ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao __rmul__ = __mul__ 31ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 32ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao def __floordiv__(self, b): 33ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if b == 0: raise ZeroDivisionError 34ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return self 35ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao __rfloordiv__ = __floordiv__ 36ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao __truediv__ = __floordiv__ 37ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao __rtuediv__ = __floordiv__ 38ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao __div__ = __floordiv__ 39ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao __rdiv__ = __floordiv__ 40ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 41ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao def __pow__(self, b): 42ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if b == 0: return 1 43ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return self 44ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaoaleph0 = Aleph0() 45ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 46ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef base(line): 47ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return line*(line+1)//2 48ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 49ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef pairToN((x,y)): 50ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao line,index = x+y,y 51ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return base(line)+index 52ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 53ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef getNthPairInfo(N): 54ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # Avoid various singularities 55ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if N==0: 56ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return (0,0) 57ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 58ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # Gallop to find bounds for line 59ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao line = 1 60ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao next = 2 61ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao while base(next)<=N: 62ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao line = next 63ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao next = line << 1 64ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 65ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # Binary search for starting line 66ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao lo = line 67ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao hi = line<<1 68ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao while lo + 1 != hi: 69ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao #assert base(lo) <= N < base(hi) 70ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao mid = (lo + hi)>>1 71ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if base(mid)<=N: 72ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao lo = mid 73ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao else: 74ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao hi = mid 75ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 76ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao line = lo 77ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return line, N - base(line) 78ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 79ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef getNthPair(N): 80ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao line,index = getNthPairInfo(N) 81ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return (line - index, index) 82ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 83ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef getNthPairBounded(N,W=aleph0,H=aleph0,useDivmod=False): 84ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao """getNthPairBounded(N, W, H) -> (x, y) 85ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 86ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao Return the N-th pair such that 0 <= x < W and 0 <= y < H.""" 87ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 88ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if W <= 0 or H <= 0: 89ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao raise ValueError,"Invalid bounds" 90ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao elif N >= W*H: 91ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao raise ValueError,"Invalid input (out of bounds)" 92ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 93ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # Simple case... 94ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if W is aleph0 and H is aleph0: 95ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return getNthPair(N) 96ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 97ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # Otherwise simplify by assuming W < H 98ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if H < W: 99ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao x,y = getNthPairBounded(N,H,W,useDivmod=useDivmod) 100ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return y,x 101ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 102ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if useDivmod: 103ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return N%W,N//W 104ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao else: 105ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # Conceptually we want to slide a diagonal line across a 106ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # rectangle. This gives more interesting results for large 107ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # bounds than using divmod. 108ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 109ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # If in lower left, just return as usual 110ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao cornerSize = base(W) 111ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if N < cornerSize: 112ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return getNthPair(N) 113ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 114ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # Otherwise if in upper right, subtract from corner 115ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if H is not aleph0: 116ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao M = W*H - N - 1 117ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if M < cornerSize: 118ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao x,y = getNthPair(M) 119ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return (W-1-x,H-1-y) 120ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 121ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # Otherwise, compile line and index from number of times we 122ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # wrap. 123ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao N = N - cornerSize 124ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao index,offset = N%W,N//W 125ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # p = (W-1, 1+offset) + (-1,1)*index 126ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return (W-1-index, 1+offset+index) 127ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef getNthPairBoundedChecked(N,W=aleph0,H=aleph0,useDivmod=False,GNP=getNthPairBounded): 128ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao x,y = GNP(N,W,H,useDivmod) 129ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao assert 0 <= x < W and 0 <= y < H 130ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return x,y 131ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 132ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef getNthNTuple(N, W, H=aleph0, useLeftToRight=False): 133ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao """getNthNTuple(N, W, H) -> (x_0, x_1, ..., x_W) 134ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 135ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao Return the N-th W-tuple, where for 0 <= x_i < H.""" 136ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 137ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if useLeftToRight: 138ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao elts = [None]*W 139ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao for i in range(W): 140ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao elts[i],N = getNthPairBounded(N, H) 141ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return tuple(elts) 142ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao else: 143ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if W==0: 144ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return () 145ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao elif W==1: 146ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return (N,) 147ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao elif W==2: 148ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return getNthPairBounded(N, H, H) 149ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao else: 150ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao LW,RW = W//2, W - (W//2) 151ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao L,R = getNthPairBounded(N, H**LW, H**RW) 152ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return (getNthNTuple(L,LW,H=H,useLeftToRight=useLeftToRight) + 153ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao getNthNTuple(R,RW,H=H,useLeftToRight=useLeftToRight)) 154ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef getNthNTupleChecked(N, W, H=aleph0, useLeftToRight=False, GNT=getNthNTuple): 155ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao t = GNT(N,W,H,useLeftToRight) 156ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao assert len(t) == W 157ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao for i in t: 158ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao assert i < H 159ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return t 160ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 161ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef getNthTuple(N, maxSize=aleph0, maxElement=aleph0, useDivmod=False, useLeftToRight=False): 162ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao """getNthTuple(N, maxSize, maxElement) -> x 163ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 164ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao Return the N-th tuple where len(x) < maxSize and for y in x, 0 <= 165ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao y < maxElement.""" 166ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 167ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # All zero sized tuples are isomorphic, don't ya know. 168ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if N == 0: 169ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return () 170ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao N -= 1 171ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if maxElement is not aleph0: 172ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if maxSize is aleph0: 173ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao raise NotImplementedError,'Max element size without max size unhandled' 174ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao bounds = [maxElement**i for i in range(1, maxSize+1)] 175ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao S,M = getNthPairVariableBounds(N, bounds) 176ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao else: 177ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao S,M = getNthPairBounded(N, maxSize, useDivmod=useDivmod) 178ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return getNthNTuple(M, S+1, maxElement, useLeftToRight=useLeftToRight) 179ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef getNthTupleChecked(N, maxSize=aleph0, maxElement=aleph0, 180ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao useDivmod=False, useLeftToRight=False, GNT=getNthTuple): 181ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao # FIXME: maxsize is inclusive 182ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao t = GNT(N,maxSize,maxElement,useDivmod,useLeftToRight) 183ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao assert len(t) <= maxSize 184ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao for i in t: 185ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao assert i < maxElement 186ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return t 187ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 188ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef getNthPairVariableBounds(N, bounds): 189ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao """getNthPairVariableBounds(N, bounds) -> (x, y) 190ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 191ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao Given a finite list of bounds (which may be finite or aleph0), 192ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return the N-th pair such that 0 <= x < len(bounds) and 0 <= y < 193ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao bounds[x].""" 194ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 195ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if not bounds: 196ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao raise ValueError,"Invalid bounds" 197ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if not (0 <= N < sum(bounds)): 198ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao raise ValueError,"Invalid input (out of bounds)" 199ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 200ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao level = 0 201ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao active = range(len(bounds)) 202ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao active.sort(key=lambda i: bounds[i]) 203ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao prevLevel = 0 204ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao for i,index in enumerate(active): 205ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao level = bounds[index] 206ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao W = len(active) - i 207ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if level is aleph0: 208ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao H = aleph0 209ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao else: 210ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao H = level - prevLevel 211ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao levelSize = W*H 212ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if N<levelSize: # Found the level 213ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao idelta,delta = getNthPairBounded(N, W, H) 214ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return active[i+idelta],prevLevel+delta 215ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao else: 216ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao N -= levelSize 217ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao prevLevel = level 218ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao else: 219ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao raise RuntimError,"Unexpected loop completion" 220ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 221ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef getNthPairVariableBoundsChecked(N, bounds, GNVP=getNthPairVariableBounds): 222ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao x,y = GNVP(N,bounds) 223ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao assert 0 <= x < len(bounds) and 0 <= y < bounds[x] 224ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return (x,y) 225ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 226ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao### 227ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 228ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef testPairs(): 229ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao W = 3 230ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao H = 6 231ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao a = [[' ' for x in range(10)] for y in range(10)] 232ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao b = [[' ' for x in range(10)] for y in range(10)] 233ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao for i in range(min(W*H,40)): 234ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao x,y = getNthPairBounded(i,W,H) 235ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao x2,y2 = getNthPairBounded(i,W,H,useDivmod=True) 236ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao print i,(x,y),(x2,y2) 237ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao a[y][x] = '%2d'%i 238ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao b[y2][x2] = '%2d'%i 239ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 240ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao print '-- a --' 241ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao for ln in a[::-1]: 242ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if ''.join(ln).strip(): 243ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao print ' '.join(ln) 244ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao print '-- b --' 245ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao for ln in b[::-1]: 246ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if ''.join(ln).strip(): 247ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao print ' '.join(ln) 248ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 249ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaodef testPairsVB(): 250ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao bounds = [2,2,4,aleph0,5,aleph0] 251ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao a = [[' ' for x in range(15)] for y in range(15)] 252ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao b = [[' ' for x in range(15)] for y in range(15)] 253ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao for i in range(min(sum(bounds),40)): 254ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao x,y = getNthPairVariableBounds(i, bounds) 255ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao print i,(x,y) 256ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao a[y][x] = '%2d'%i 257ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 258ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao print '-- a --' 259ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao for ln in a[::-1]: 260ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao if ''.join(ln).strip(): 261ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao print ' '.join(ln) 262ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 263ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao### 264ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 265ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao# Toggle to use checked versions of enumeration routines. 266ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaoif False: 267ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao getNthPairVariableBounds = getNthPairVariableBoundsChecked 268ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao getNthPairBounded = getNthPairBoundedChecked 269ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao getNthNTuple = getNthNTupleChecked 270ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao getNthTuple = getNthTupleChecked 271ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 272ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaoif __name__ == '__main__': 273ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao testPairs() 274ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 275ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao testPairsVB() 276ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 277