Listing all monotone binary functions

Question

A monotone binary function is defined as follows:

Given binary vectors $\bf x$ and $\bf y$ (each having $n$ bits) with $\bf x\geq \bf y$, a function $f:\bf x\rightarrow\{0,1\}$ is called monotone if $$f(\bf x)\geq \it f(\bf y)$$

Here $\bf x\geq \bf y$ means $x_i\geq y_i$ for all $i$.

Example: $n=3$, binary vector $\bf x$ takes the following values:

000
001
010
011
100
101
110
111

Here if $f(001)=1$ then $f(011)=1$, $f(101)=1$, $f(111)=1$ must be true. Assume also that $f(000)=0$, then if $f(010)=1$, $f(110)=1$ is another must.The last one $f(100)=0$ and $f(100)=1$ can also be chosen. Accordingly two valid vectors are

$$f_1=\{0,1,1,1,0,1,1,1\}\, \mbox{and}\, f_2=\{0,1,1,1,1,1,1,1\}$$

I am looking for an algorithm to list all such posible vectors. I can do it with exhaustive search but I have the feeling that there should be an effective way of finding all such vectors given $n$.

Do you have any ideas about how to go about this problem?

Answer 1

ClearAll[lessEqual, monotonicQ, monotonicSequences]
lessEqual[n_Integer] := And @@ Thread[LessEqual @@ IntegerDigits[{##}, 2, n]] &
monotonicQ[n_] := Function[x, And @@ 
  Join[If[lessEqual[n][##], x[#] <= x[#2], ## &[]] & @@@ Subsets[Range[0, 2^n - 1], {2}], 
     Array[0 <= x[#] <= 1 &, 2^n, 0]]]
monotonicSequences = Module[{s = Array[x, 2^#, 0]}, 
   s /. Solve[monotonicQ[#][x], s, Integers] ] &;

Examples:

Length[monotonicSequences@#] & /@ Range[2, 5]

{6, 20, 168, 7581}

monotonicSequences @ 2 // Column // TeXForm

$\begin{array}{l} \{0,0,0,0\} \\ \{0,0,0,1\} \\ \{0,0,1,1\} \\ \{0,1,0,1\} \\ \{0,1,1,1\} \\ \{1,1,1,1\} \\ \end{array}$

monotonicSequences@3 // Column // TeXForm

$\begin{array}{l} \{0,0,0,0,0,0,0,0\} \\ \{0,0,0,0,0,0,0,1\} \\ \{0,0,0,0,0,0,1,1\} \\ \{0,0,0,0,0,1,0,1\} \\ \{0,0,0,0,0,1,1,1\} \\ \{0,0,0,0,1,1,1,1\} \\ \{0,0,0,1,0,0,0,1\} \\ \{0,0,0,1,0,0,1,1\} \\ \{0,0,0,1,0,1,0,1\} \\ \{0,0,0,1,0,1,1,1\} \\ \{0,0,0,1,1,1,1,1\} \\ \{0,0,1,1,0,0,1,1\} \\ \{0,0,1,1,0,1,1,1\} \\ \{0,0,1,1,1,1,1,1\} \\ \{0,1,0,1,0,1,0,1\} \\ \{0,1,0,1,0,1,1,1\} \\ \{0,1,0,1,1,1,1,1\} \\ \{0,1,1,1,0,1,1,1\} \\ \{0,1,1,1,1,1,1,1\} \\ \{1,1,1,1,1,1,1,1\} \\ \end{array}$

First[RepeatedTiming[monotonicSequences @ #]] & /@ {2, 3, 4, 5}

{0.0019, 0.0064, 0.0380, 2.25}

Answer 2

Here's an approach using Reduce.

The first step is to construct all of the inequalities. Consider a bit vector $b(1, 0, 1, 0)$. The inequalities that can be generated with this vector are $b(1, 0, 1, 0 \ge b(0, 0, 1, 0)$ and $b(1, 0, 1, 0) \ge b(1, 0, 0, 0)$. Basically, for each bit vector, subtract 1 from each nonzero position, and create the inequality. Here is some code that does this:

monotone[n_, max_] := Module[{ineq, tup, z = Array[w, 2^n, 0]},
    eqns = Flatten @ Table[
        If[Min[t - UnitVector[n, k]]>=0,
            w[toNumber[t, n]] >= w[toNumber[t-UnitVector[n,k], n]],
            Nothing
        ],
        {t, Rest @ Tuples[Range[0, 1], n]},
        {k, n}
    ];
    res = Reduce[
        And@@eqns && Min[z]>=0 && Max[z]<=max,
        z,
        Integers
    ];
    Values @ {ToRules @ res}
]

toNumber[t_, n_] := NumberCompose[t, 2^Range[n-1, 0, -1]]

Let's check the two simple cases:

monotone[2, 1]
% //Length

{{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 1, 1}, {0, 1, 0, 1}, {0, 1, 1, 1}, {1, 1, 1, 1}}

6

monotone[3, 1]
% //Length

{{0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 0, 1, 1, 1}, {0, 0, 0, 0, 1, 1, 1, 1}, {0, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 1, 1}, {0, 0, 0, 1, 0, 1, 0, 1}, {0, 0, 0, 1, 0, 1, 1, 1}, {0, 0, 0, 1, 1, 1, 1, 1}, {0, 0, 1, 1, 0, 0, 1, 1}, {0, 0, 1, 1, 0, 1, 1, 1}, {0, 0, 1, 1, 1, 1, 1, 1}, {0, 1, 0, 1, 0, 1, 0, 1}, {0, 1, 0, 1, 0, 1, 1, 1}, {0, 1, 0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 0, 1, 1, 1}, {0, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}}

20

The case with $n=4$ takes a bit more time:

s = monotone[4, 1]; //AbsoluteTiming
s //Length

{37.3793, Null}

168

in agreement with the linked reference. Finally, an example that isn't just 0s and 1s:

monotone[2, 2]
% //Length

{{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 2}, {0, 0, 1, 1}, {0, 0, 1, 2}, {0, 0, 2, 2}, {0, 1, 0, 1}, {0, 1, 0, 2}, {0, 1, 1, 1}, {0, 1, 1, 2}, {0, 1, 2, 2}, {0, 2, 0, 2}, {0, 2, 1, 2}, {0, 2, 2, 2}, {1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 2}, {1, 2, 1, 2}, {1, 2, 2, 2}, {2, 2, 2, 2}}

20