コミット: 20425dba992f751cf23c32030deb7685fc6bb85b - catabase (git)

A database of categories

コミットメタ情報

• リビジョン: 20425dba992f751cf23c32030deb7685fc6bb85b (tree)
• 日時: 2023-12-29 13:32:25
• 作者: Corbin <cds@corb...>
• コミッター: Corbin

ログメッセージ

And this too.

変更サマリ

• add: stone.py

差分

--- /dev/null
+++ b/stone.py
@@ -0,0 +1,103 @@
+from collections import deque
+from itertools import combinations
+import operator
+import random
+
+def randDim(): return random.choice(list(range(2, 8)))
+
+def discreteness(r, c):
+    p = 2 ** c - r
+    q = 2 ** r - c
+    return (p - q) / (p + q)
+
+def randomSpace():
+    r = randDim()
+    c = randDim()
+    return tuple(tuple(random.choice([False, True]) for _ in range(c))
+                 for _ in range(r))
+
+def transpose(s): return tuple(map(tuple, zip(*s)))
+
+def addRow(s, v): return s + (tuple(v for _ in range(len(s[0]))),)
+def addZeroRow(s): return addRow(s, False)
+def addZeroColumn(s): return transpose(addZeroRow(transpose(s)))
+def addOneColumn(s): return transpose(addRow(transpose(s), True))
+
+def dims(s): return len(s), len(s[0])
+
+def collapse(s):
+    done = False
+    while not done:
+        t = tuple(set(s))
+        u = transpose(tuple(set(transpose(t))))
+        done = dims(s) == dims(t) == dims(u)
+        s = u
+    return s
+
+def closeOverOps(s, *ops):
+    # NB: closure over rows only!
+    d = deque(s)
+    rs = set(s)
+    while d:
+        r = d.pop()
+        closure = set(op(r, x) for x in rs for op in ops) - rs
+        rs |= closure
+        d.extendleft(closure)
+    return tuple(rs)
+
+def makeOp(f):
+    return lambda r1, r2: tuple(f(x, y) for x, y in zip(r1, r2))
+
+union = makeOp(operator.or_)
+intersection = makeOp(operator.and_)
+xor = makeOp(operator.xor)
+
+def topSpace(s):
+    # Closure over empty intersections is equivalent to an all-ones column.
+    s = addOneColumn(s)
+    return collapse(transpose(closeOverOps(transpose(s), union, intersection)))
+
+def unionPoset(s):
+    p = set((i, j) for ((i, x), (j, y))  in combinations(enumerate(s), 2)
+            if all(map(operator.le, x, y)))
+    p |= set((j, i) for ((i, x), (j, y))  in combinations(enumerate(s), 2)
+             if all(map(operator.ge, x, y)))
+    return p
+
+def assigns(w):
+    for i in range(2 ** w):
+        yield tuple(bool((i >> k) & 1) for k in reversed(range(w)))
+
+def implies(p, q): return (not p) or q
+
+def antichains(p, w):
+    # NB: #P-complete! See https://cs.stackexchange.com/a/83954/131656
+    for r in assigns(w):
+        if all(implies(r[s], r[d]) for (s, d) in p): yield r
+
+def semilat(s):
+    s = addZeroColumn(s)
+    s = closeOverOps(s, union)
+    s = collapse(s)
+    p = unionPoset(s)
+    s += tuple(antichains(p, len(s)))
+    return collapse(s)
+
+def distlat(s):
+    s = addOneColumn(addZeroColumn(s))
+    return collapse(closeOverOps(s, union, intersection))
+
+def complat(s):
+    s = closeOverOps(transpose(addOneColumn(s)), intersection)
+    s = closeOverOps(transpose(addOneColumn(s)), intersection)
+    return collapse(s)
+
+def vectorSpace(s):
+    s = closeOverOps(transpose(s), xor)
+    s = closeOverOps(transpose(s), xor)
+    s = addZeroColumn(addZeroRow(s))
+    return collapse(s)
+
+def findRange(ss):
+    r = set(discreteness(*dims(s)) for s in ss)
+    return min(r), max(r)