selectoropt.py

#!/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))

Improved version here.