multinomial

commit df31afe4fdd905e10fe289275ef3f0347b23f606
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Mon, 21 Nov 2016 17:55:00 +0000

initial

Diffstat:
main.py
 | 
48
++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 48 insertions(+), 0 deletions(-)
diff --git a/main.py b/main.py
@@ -0,0 +1,48 @@
+#!/usr/bin/python3
+
+# compute undirected graph of configurations for efficient multinomial
+# coefficient computation in SWERC'16 problem H
+
+# use as: ./main.py MASS DIMENSIONS > graph.dot
+# then compile graph with: dot -Tps graph.dot > graph.ps
+
+import sys
+
+def tples(n, h, l=None):
+    if l == None:
+        l = n+1
+    if n == 0:
+        return [()]
+    if h == 0:
+        return []
+    lo = []
+    for i in range(min(n, l)):
+        r = tples(n-i-1, h-1, i+1)
+        for t in r:
+            lo.append(tuple([i+1] + list(t)))
+    return lo
+
+def adj(l1, l2):
+    if abs(len(l1) - len(l2)) > 1:
+        return False
+    if len(l2) > len(l1):
+        return adj(l2, l1)
+    if len(l1) > len(l2):
+        l2a = list(l2) + [0]
+    else:
+        l2a = list(l2)
+    s = sum(abs(x - y) for (x, y) in zip(l1, l2a))
+    return s == 2
+
+if __name__ == '__main__':
+    ml = tples(int(sys.argv[1]), int(sys.argv[2]))
+    print("graph G {")
+    for i in range(len(ml)):
+        print('n%d[label="%s"];' % (i, ml[i]))
+    for i in range(len(ml)):
+        for j in range(len(ml)):
+            if i < j:
+                if adj(ml[i], ml[j]):
+                    print("n%d -- n%d;" % (i, j))
+    print("}")
+