chiark / gitweb /
Another way to make up dissections easily.
authorSimon Tatham <anakin@pobox.com>
Mon, 17 Mar 2014 18:40:34 +0000 (18:40 +0000)
committerSimon Tatham <anakin@pobox.com>
Mon, 17 Mar 2014 18:40:34 +0000 (18:40 +0000)
If n-m is still bigger than m, then we can take the dissection for
(n-m,m) and extend it by adding on an m-stick to each n-stick.

tabulate.py

index 564261c..29caaae 100755 (executable)
@@ -41,6 +41,16 @@ def verify(n, m, dissection):
     assert total == n
     assert collections[0] == collections[1]
 
+def add_m_dissector(n,m):
+    if n <= 2*m:
+        return None
+    prev = dissections[(n-m, m)]
+    ret = [prev[0][:], prev[1][:]]
+    for i in range(len(ret[0])):
+        ret[0][i] = (ret[0][i][0], ret[0][i][1] + [m])
+    ret[1].append((m, (m,)))
+    return ret
+
 def gcd_dissector(n,m):
     gcd = fractions.gcd(n,m)
     return [[(m, (gcd,) * (n/gcd))],
@@ -51,6 +61,7 @@ def invent_dissection(n,m):
     best = 0
     for dissector, this_reason in [
         (gcd_dissector, "trivial gcd solution"),
+        (add_m_dissector, "extend solution for (%d,%d)" % (n-m, m)),
         ]:
         dissection = dissector(n, m)
         if dissection is None: continue