numpymatrixpython-itertools

Create all possible outcomes from numpy matrices that show disjoints and subsets

Let's assume there is an event and within this event there are multiple outcomes that can co-exist. An example would be a tennis game where A plays against B and B serves. A couple of possible outcomes are possible:

The following relationships are evident:

A wins with 60-0 and A wins with 60-15 are both a subset of A wins. A wins and B wins are disjoints. The same applies for A wins with 60-0 and A wins with 60-15 and A wins with 60-0 and B scores an ace.

I create a matrix that shows whether the m-column and n-row are disjoints or not. Basically, this matrix shows which events are compatible with each other.

import numpy as np


D = np.array([
    [0, 1, 0, 0, 0],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 1, 1],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0]
])

So, the second row represents the outcome that B wins. In this case the outcomes, except B scores an ace are impossible. and therefore 1. The last row represent that B scores an ace which is possible in every outcome except A wins with 60-0.

In addition, I have a matrix, S, that imply which events are subsets of each other.

S = np.array([
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
])

Both A wins with 60-0 or A wins with 60-15 are a subset of A wins.

I want to create a matrix with all the possible outcomes. In this particular case the matrix would look as follows

X = np.array([
    [1, 0, 0, 0, 0],      # A wins with 60-30, B scores no ace
    [1, 0, 1, 0, 0],      # A wins with 60-0
    [1, 0, 0, 1, 0],      # A wins with 60-15, B scores no ace
    [1, 0, 0, 1, 1],      # A wins with 60-15, B scores ace
    [1, 0, 0, 0, 1],      # A wins with 60-30, B scores ace
    [0, 1, 0, 0, 0],      # B wins with 15-60, B scores no ace
    [0, 1, 0, 0, 1]       # B wins with 0-60,  B scores ace
])

There are a lot more possible outcomes within a tennis match, so I would like to create a function where the variables D and S would be the input and X would be the output.

My attempt so far looks as follows:

import numpy as np
from itertools import product


D = np.array([
    [0, 1, 0, 0, 0],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 1, 1],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0]
])


S = np.array([
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
])


def combinations(n: int, D: np.ndarray, S: np.ndarray):
    combs = list(product([1, 0], repeat=n))

    def disjoint(comb):
        for (i, j) in zip(*np.nonzero(D)):
            if comb[i] == 1 and comb[j] == 1:
                return True

    def subset(comb):
        for (i, j) in zip(*np.nonzero(S)):
            if np.sign(comb[i]) != np.sign(comb[j]):
                return True

    combs = [comb for comb in combs if not disjoint(comb)]
    # combs = [comb for comb in combs if not subset(comb)]
    
    return np.array(combs)


n = 5 
c = combinations(n, D, S)
print(c)

The output is partially correct.

[[1 0 1 0 0]
 [1 0 0 1 1]
 [1 0 0 1 0]
 [1 0 0 0 1]
 [1 0 0 0 0]
 [0 1 0 0 1]
 [0 1 0 0 0]
 [0 0 1 0 0]
 [0 0 0 1 1]
 [0 0 0 1 0]
 [0 0 0 0 1]
 [0 0 0 0 0]]

How can I write the subset-filter in such a way that the wrong combinations are excluded?

Solution

  • I would formulate your problem as a series of implications of events (for an alternative using truth tables of variable pairs, see Update 2 below): Which event that happens (or does not happen) implies that another event happens (or does not happen)?

    You have the following events:

    I came up with the following implications (to be read as "row implies column"):

    a ~a b ~b c ~c d ~d e ~e
    a 1 1
    ~a 1 1
    b 1 1 1 1
    ~b 1 1
    c 1 1 1 1 1
    ~c 1
    d 1 1 1 1
    ~d 1
    e 1 1
    ~e 1

    Take as an example c's row, which contains the implications:

    c → a, c → ~b, c → c, c → ~d, c → ~e

    This can be read as:

    We can skip the trivial cases (the ones implying themselves, on the diagonal) and are left with 14 implications. We can then find all solutions that satisfy the implications programmatically, for example with sympy (where implications are written with the >> operator):

    from sympy import symbols
from sympy.logic.inference import satisfiable

a, b, c, d, e = symbols("a b c d e")

expr = (( a >> ~b) & (~a >>  b) & ( b >> ~a) & ( b >> ~c) & ( b >> ~d) &
        (~b >>  a) & ( c >>  a) & ( c >> ~b) & ( c >> ~d) & ( c >> ~e) &
        ( d >>  a) & ( d >> ~b) & ( d >> ~c) & ( e >> ~c))

for comb in satisfiable(expr, all_models=True):
    keys = sorted(comb.keys(), key=lambda s: s.name)
    print(", ".join([f"{k.name}={int(comb[k])}" for k in keys]))
# a=1, b=0, c=0, d=0, e=0
# a=1, b=0, c=0, d=0, e=1
# a=1, b=0, c=0, d=1, e=0
# a=1, b=0, c=0, d=1, e=1
# a=1, b=0, c=1, d=0, e=0
# a=0, b=1, c=0, d=0, e=0
# a=0, b=1, c=0, d=0, e=1

    Update: We can also start out from a NumPy array that encodes the given table:

    import numpy as np
from sympy import symbols, And
from sympy.logic.inference import satisfiable

a = np.asarray([[1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
                [0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
                [0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
                [1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
                [1, 0, 0, 1, 1, 0, 0, 1, 0, 1],
                [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
                [1, 0, 0, 1, 0, 1, 1, 0, 0, 0],
                [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
                [0, 0, 0, 0, 0, 1, 0, 0, 1, 0],
                [0, 0, 0 ,0, 0, 0, 0, 0, 0, 1]])

# Sanity check: square matrix with even number of entries?
assert (a.shape[0] == a.shape[1]) and (not len(a) % 2)

n = len(a) // 2
variables = symbols(f"x0:{n}")

implications = []
for row in range(n):
    for col in range(n):
        # Optionally, we could also skip the trivial cases (row == col) here
        if a[2 * row, 2 * col]:
            implications.append(variables[row] >> variables[col])
        if a[2 * row, 2 * col + 1]:
            implications.append(variables[row] >> ~variables[col])
        if a[2 * row + 1, 2 * col]:
            implications.append(~variables[row] >> variables[col])
        if a[2 * row + 1, 2 * col + 1]:
            implications.append(~variables[row] >> ~variables[col])

for comb in satisfiable(And(*implications), all_models=True):
    keys = sorted(comb.keys(), key=lambda s: s.name)
    print(", ".join([f"{k.name}={int(comb[k])}" for k in keys]))
# x0=1, x1=0, x2=0, x3=0, x4=0
# x0=1, x1=0, x2=0, x3=1, x4=0
# x0=1, x1=0, x2=0, x3=0, x4=1
# x0=1, x1=0, x2=0, x3=1, x4=1
# x0=1, x1=0, x2=1, x3=0, x4=0
# x0=0, x1=1, x2=0, x3=0, x4=0
# x0=0, x1=1, x2=0, x3=0, x4=1

    Update 2: A more straightforward and less error-prone way, I guess, would be looking at all possible combinations of all pairs of variables separately, by means of truth tables. For each combination, one would ask the question, whether it is possible or not. This would lead to the following truth tables, for which we could then look up corresponding logical operations:

    For a programmatic approach, I guess I would solve the mapping of the truth table to the corresponding operations via a lookup table (there are only 2⁴=16 possible outcomes for truth tables of two variables). In any case, once we have the operations, we can again use e.g. sympy for solving:

    from sympy import symbols
from sympy.logic.boolalg import Nand, Xor
from sympy.logic.inference import satisfiable

a, b, c, d, e = symbols("a b c d e")

expr = Xor(a, b) & (c >> a) & (d >> a) & Nand(b, c) & Nand(b, d) & Nand(c, d) & Nand(c, e)

for comb in satisfiable(expr, all_models=True):
    keys = sorted(comb.keys(), key=lambda s: s.name)
    print(", ".join([f"{k.name}={int(comb[k])}" for k in keys]))
# a=1, b=0, c=0, d=0, e=0
# a=1, b=0, c=0, d=0, e=1
# a=1, b=0, c=0, d=1, e=0
# a=1, b=0, c=0, d=1, e=1
# a=0, b=1, c=0, d=0, e=0
# a=0, b=1, c=0, d=0, e=1
# a=1, b=0, c=1, d=0, e=0