This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
from collections import deque | |
from math import inf | |
import json | |
# For simplicity use the same disjoint-set data structure as for the | |
# permutation argument. | |
class DisjointSets(object): | |
def __init__(self, n): | |
self.n = n | |
self.mapping = [i for i in range(n)] | |
self.aux = [i for i in range(n)] | |
self.sizes = [1]*n | |
def copy(self, left, right): | |
# if left and right are in the same cycle, do nothing | |
leftcycle = self.aux[left] | |
rightcycle = self.aux[right] | |
if leftcycle == rightcycle: | |
return | |
# merge the smaller cycle into the bigger one | |
if self.sizes[leftcycle] < self.sizes[rightcycle]: | |
(leftcycle, rightcycle) = (rightcycle, leftcycle) | |
self.sizes[leftcycle] += self.sizes[rightcycle] | |
i = rightcycle | |
while True: | |
self.aux[i] = leftcycle | |
i = self.mapping[i] | |
if i == rightcycle: break | |
(self.mapping[left], self.mapping[right]) = (self.mapping[right], self.mapping[left]) | |
def __repr__(self): | |
return "DisjointSets(%r) {\n mapping = %r\n aux = %r\n sizes = %r\n}" % (self.n, self.mapping, self.aux, self.sizes) | |
"""Iterate through combinations with one entry chosen from each disjoint set.""" | |
def iter_combinations(self, degrees, degree_bound): | |
i = 0 | |
while i < self.n: | |
combination = deque() | |
seen = [False]*self.n | |
d = 0 | |
for cycle in range(self.n): | |
#print("cycle =", cycle) | |
next = self.mapping[cycle] | |
#print("next =", next) | |
if next is None: | |
continue | |
aux = self.aux[cycle] | |
if seen[aux]: | |
continue | |
new_d = max(d, degrees[next]) | |
#print("new_d =", new_d) | |
if new_d + len(combination) + 1 > degree_bound: | |
#print("skipping") | |
continue | |
d = new_d | |
self.mapping[cycle] = self.mapping[next] | |
# next might equal cycle, in which case we set the final remaining entry | |
# in this cycle to None, excluding it from later combinations. | |
self.mapping[next] = None | |
# Don't repeat entries from the same cycle in a combination. | |
seen[aux] = True | |
i += 1 | |
combination.append(next) | |
combination = sorted(combination) | |
#print("combination =", combination) | |
assert d == max([degrees[s] for s in combination]), d | |
d += len(combination) | |
#print("d =", d) | |
yield combination | |
def compute_combinations(selectors, width, degrees, degree_bound): | |
print("selectors:") | |
for row in selectors: | |
print(row) | |
print("\ndegrees:") | |
print(degrees) | |
print("degree_bound =", degree_bound) | |
print("") | |
assert len(degrees) == width | |
# Compute a disjoint-set data structure in which two selectors | |
# are in the same set iff they are excluded from being combined. | |
X = DisjointSets(width) | |
prev = [0]*width | |
for row in selectors: | |
assert len(row) == width | |
# Optimization: if selectors set in the current row are | |
# a subset of those in some previous row, then this row | |
# can be skipped. | |
if is_subset(row, prev): | |
continue | |
# Each pair of selectors set in this row are excluded | |
# from being combined. | |
selected = [h for h in range(width) if row[h] == 1] | |
for (i, j) in enumerate(selected): | |
for k in selected[:i]: | |
print("%r <-> %r" % (j, k)) | |
X.copy(j, k) | |
prev = row | |
print(repr(X)) | |
return list(X.iter_combinations(degrees, degree_bound)) | |
def is_subset(xs, ys): | |
for (x, y) in zip(xs, ys): | |
if x > y: | |
return False | |
return True | |
def transpose(M): | |
cols = len(M) | |
rows = len(M[0]) | |
print("cols =", cols) | |
print("rows =", rows) | |
return [[M[col][row] for col in range(cols)] for row in range(rows)] | |
""" | |
selectors = [ | |
[0, 0, 0, 0, 1], | |
[1, 0, 0, 0, 1], | |
[0, 1, 1, 0, 0], | |
[0, 1, 0, 0, 0], | |
[0, 0, 1, 1, 0], | |
] | |
degree_bound = 9 | |
degrees = ( | |
[3, 6, 5, 8, 2] | |
) | |
""" | |
with open("action-circuit-selectors.json") as f: | |
content = json.loads(f.read()) | |
selectors = transpose(content["selectors"]) | |
width = len(selectors[0]) | |
degree_bound = inf | |
degrees = [0]*width | |
print(compute_combinations(selectors, width, degrees, degree_bound)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Improved version here.