Instantly share code, notes, and snippets.

# daira/selectoropt.py

Created July 20, 2021 12:40
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 = *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 = *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) 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) degree_bound = inf degrees = *width print(compute_combinations(selectors, width, degrees, degree_bound))

### daira commented Jul 20, 2021

Improved version here.