How to determine all cases consistent with constraints

Question

Suppose that $(i, j), (k, l)$ and $(m, n)$ are pairs of non-negative integers, satisfying the following constraints:

$$i < j,\;\; k < l, \;\; m < n$$

and

$$ (i, j) < (k, l) < (m, n)$$

...where the ordering of the pairs implied by the last set of inequalities is the lexicographic one (e.g. $(i, j) < (k, l)$ iff either (1) $i < k$, or else (2) $i = k$ and $j < l$).

For each possible cardinality of the set $\{i,j,k,l,m,n\}$, I would like to find, subject to the constraints above, all the possible configurations of equality and inequality relationships among elements of the set that would yield such a cardinality. For example, cardinality 3, one such configuration would be

$$i = k, j = m, l = n$$

The brute-force solution to this problem would be to generate all possible configurations of equality/inequality relationships among the six variables, weed out the ones that are inconsistent (either internally or relative to the constraints), and finally classify the remaining configurations according to the cardinality they imply.

I think I can write the Mathematica code to generate all the possible configurations, but I'm not sure how to weed out the ones that are inconsistent, or incompatible with the constraints.

To give an example of what I mean by "configuration", consider the simpler problem where we have only three variables $i, j, k$, and only one constraint, $i < j$. The following are three possible configurations:

$$i < j,\;\; j < k, \;\; i < k$$ $$i < j,\;\; j = k, \;\; k = i$$ $$i > j,\;\; j > k, \;\; i > k$$

The first one is OK, the second one is internally inconsistent, and the third one is incompatible with the constraint.

When I enter the above expressions in Mathematica, it just returns them verbatim:

In[1]:= i < j && j < k && i < k
Out[1]= i < j && j < k && i < k
In[2]:= i < j && j == k && i == k
Out[2]= i < j && j == k && i == k

(I had hoped that the first expression would have evaluated to True and the second one to False.)

Does Mathematica provide a convenient way to weed out the invalid configurations?

Answer 1

The possible cardinalities $c+1$ of the set $\{i,j,k,l,m,n\}$ are, of course, $1$ through $6$ inclusive, corresponding to $c=0$ through $5$. Because the question concerns only the relative orders of its elements, then we may--without any loss of generality--replace the elements by their ranks from $0$ (for the smallest) through $c$.

Because the answers I will obtain differ from those offered in another reply, I am going to proceed as carefully as possible so that any possible misunderstandings will be clearly exposed. This solution progresses in two steps, as suggested in the question: a brute-force listing of "partial" solutions, or "candidates," followed by a further test to select those that are truly solutions. It's easy to check that these tests implement the criteria of the question, so the crux of the matter is to verify that this procedure generates all possible solutions.

Step 1: assuring the first set of inequalities

To assure that $i\lt j$, $k\lt l$, and $m\lt n$, use Table to enumerate all such partial solutions:

 Flatten[Table[{{i, j}, {k, l}, {m, n}}, 
  {i, 0, c}, {j, i + 1, c}, {k, i, c}, {l, k + 1, c}, {m, k, c}, {n, m + 1, c}], 5]

The output is a list of lists in the form $\{\{i,j\},\{k,l\},\{m,n\}\}$. The tabulation clearly assures the three inequalities; I claim it produces all possible solutions to those three inequalities. I hope the claim is clear, because the tabulation makes the ranges of $i,\ldots,n$ as wide as possible subject to the three constraints. All the ranges have the largest possible upper limit of $c$. The lower limit of $0$ for the $i$ range is unexceptional. $j\gt i$ implies $j \ge i+1$ justifies the lower limit of the $j$ range. $(i,j)\lt(k,l)$ implies $i\le k$, justifying the lower limit of $i$ for the $k$ range. The other three lower limits are similarly justified.

It is also clear, since all ranges run from $0$ through $c$, that the cardinalities cannot exceed $c+1$. However, they could be less than that. We will have to watch out for this below.

Step 2: assuring the lexicographic inequalities

The preceding tabulation includes too much: the lexicographic inequalities might not be satisfied. Use Select to pick out the tabulated sequences that satisfy these inequalities. In addition, to assure that precisely the requested cardinality is achieved, adjoin a cardinality check to the selection criterion.

This is sufficiently straightforward that at this juncture I will offer the full solution, encapsulated in a Module:

f[card_Integer] := Module[{c = card - 1, lt, good},
   lt[{i_, j_}, {k_, l_}] := i < k || (i == k && j < l); (* Lexicographic order *)
   good[{{i_, j_}, {k_, l_}, {m_, n_}}] := {i, j}~lt~{k, l} && {k, l}~lt~{m, n};
   Select[Flatten[Table[{{i, j}, {k, l}, {m, n}}, 
     {i, 0, c}, {j, i + 1, c}, {k, i, c}, {l, k + 1, c}, {m, k, c}, {n, m + 1, c}], 5],
     good[#] && Length[Union[Flatten[#]]] == card &]];

The function good checks the lexicographic order. The final criterion on the length winnows out any candidates whose cardinality is too small.

It will become evident that this solution could be made more efficient: for instance, we can always take $i=0$. But no matter: it is most important that the solution be as clear and convincing as possible; speed improvements will be unnecessary.

The solutions

To assess the scope of the solutions, let's generate and count them all:

Length /@ f /@ Range[6] // AbsoluteTiming

$\{0.0140008,\{0,0,1,16,30,15\}\}$

The code is fast and has generated $62$ solutions for cardinalities through $6$. Their numbers are small enough to let us inspect them.

f[3]

$\{\{\{0,1\},\{0,2\},\{1,2\}\}\}$

That is, $i=k=0$ are the two smallest values, $j=m=1$ are the next two, and $l=n=2$ the largest. This is the solution named in the question itself. It might be written in the form

$$i = k \lt j = m \lt l = n.$$

We should, however, be wary of such "configuration" notation because it is not at all clear what constitutes a "configuration" nor even how to tell (a) what information is needed to specify a configuration unambiguously, (b) whether two configurations specify the same solution, or (c) how easily to verify that a putative configuration is self-consistent.

It is more convenient to use a visual representation when inspecting larger numbers of solutions. Let's draw smaller values in darker colors, graduating to lighter ones:

display[f_List] := Grid[Partition[ArrayPlot[#, ColorFunction->"BlueGreenYellow"]& /@ f, 8,8,1,""],
  ItemSize -> 3]

Thus the preceding cardinality-$3$ solution will use just three distinct colors:

display[f[3]]

The squares in this tableau are arranged to correspond to the solution

$\left( \begin{array}{cc} i & j \\ k & l \\ m & n \end{array} \right)$

Visually, the constraints of the question translate to

1. Each right-hand square must be brighter than its neighbor to the left.

2. Each row must be brighter than the one above it, in the lexicographic sense: either its left square is brighter or, if the left squares are the same color, the right square is brighter.

3. The number of distinct colors must equal the desired cardinality.

Here, then, are all the remaining solutions arranged by cardinality (numbers of distinct colors):

display[f[4]]

display[f[5]]

display[f[6]]

Answer 2

Method 1: Resolve

The idea is to use the following piece of code:

Resolve@Exists[{i, j, k}, i < j && j < k && i < k] (* True *)
Resolve@Exists[{i, j, k}, i < j && j == k && i == k] (* False *)

Here is a complete solution.

lex[{i_, j_}, {k_, l_}] := i < k || i == k && j < l
pairCond[{i_, j_}, {k_, l_}] := i < j && k < l && lex[{i, j}, {k, l}]

splitAt[set_List, {}] := {set}
splitAt[set_List, {p_, r___}] := {Take[set, p]} ~ Join ~ splitAt[Drop[set, p], {r} - p]

partitions[set_List, n_Integer?Positive] /; n <= Length[set] := splitAt[set, #] & /@ Subsets[Range[Length[set] - 1], {n - 1}]

configuration[part_List] := And @@ Join[Equal @@@ part, MapThread[Less, {Last /@ Most@part, First /@ Rest@part}]]

isConsistent[vars_, condition_, configuration_] := Resolve@Exists[vars, condition && configuration]

vars = {i, j, k, l, m, n};
condition = pairCond[{i, j}, {k, l}] && pairCond[{k, l}, {m, n}];
permutations = Cases[Permutations[vars], Except[{___, j, ___, i, ___} | {___, l, ___, k, ___} | {___, n, ___, m, ___}]];
selectTable = Table[Module[{unsorted, sorted},
     unsorted = Flatten[partitions[#, card] & /@ permutations, 1];
     sorted = Union@Map[Sort, unsorted, {2}];
     Select[sorted, isConsistent[vars, condition, configuration@#] &]],
    {card, 1, Length@vars}]; // Timing
Length /@ selectTable

Now the variable selectTable holds the solutions, gathered by cardinality. You can view them with Map[configuration, selectTable, {2}].

If someone needs help, I can clarify any part of the code. By the way, the number of solutions for cardinality 1 through 6 are {0, 0, 1, 16, 30, 15}.

Method 2: Pattern matching

This solution is faster (30x). It is based on pattern matching. I think it is instructive.

vars = {i, j, k, l, m, n};
condition = pairCond[{i, j}, {k, l}] && pairCond[{k, l}, {m, n}];
permutations = Cases[Permutations[vars], Except[{___, j, ___, i, ___} | {___, l, ___, k, ___} | {___, n, ___, m, ___}]];

dnf = BooleanConvert[condition, "DNF"];
cnf = BooleanConvert[condition, "CNF"];

toPatternsRule = {
    x_ < y_ :> {___, {___, x, ___}, ___, {___, y, ___}, ___},
    x_ == y_ :> {___, {___, x, ___, y, ___}, ___} | {___, {___, x, ___, y, ___}, ___}};

dnfPatt = dnf /. toPatternsRule;
cnfPatt = cnf /. toPatternsRule;

Then you can either do

pattTable = Table[Module[{unsorted, sorted},
     unsorted = Flatten[partitions[#, card] & /@ permutations, 1];
     sorted = Union@Map[Sort, unsorted, {2}];
     Fold[Cases, sorted, #] & /@ dnfPatt /. Or -> Join],
    {card, 1, Length@vars}]; // Timing
Length /@ pattTable

or

pattTable = Table[Module[{unsorted, sorted},
     unsorted = Flatten[partitions[#, card] & /@ permutations, 1];
     sorted = Union@Map[Sort, unsorted, {2}];
     Fold[Cases, sorted, cnfPatt /. Or -> Alternatives]],
    {card, 1, Length@vars}]; // Timing
Length /@ pattTable

(using Disjunctive/Conjunctive Normal Form).

8 variables

This can be generalized to 8 variables: $$ \begin{align}{c} i<j, \quad k<l, \quad m<n, \quad o<p (i,j) < (k,l) < (m,n) < (o,p) \end{align} $$

vars = {i, j, k, l, m, n, o, p};
condition = pairCond[{i, j}, {k, l}] && pairCond[{k, l}, {m, n}] && pairCond[{m, n}, {o, p}];
permutations = Cases[Permutations[vars], Except[{___, j, ___, i, ___} | {___, l, ___, k, ___} | {___, n, ___, m, ___} | {___, p, ___, o, ___}]];

dnf = BooleanConvert[condition, "DNF"];
cnf = BooleanConvert[condition, "CNF"];

toPatternsRule = {
    x_ < y_ :> {___, {___, x, ___}, ___, {___, y, ___}, ___},
    x_ == y_ :> {___, {___, x, ___, y, ___}, ___} | {___, {___, x, ___, y, ___}, ___}};

dnfPatt = dnf /. toPatternsRule;
cnfPatt = cnf /. toPatternsRule;

pattTable = Table[Module[{unsorted, sorted},
     unsorted = Flatten[partitions[#, card] & /@ permutations, 1];
     sorted = Union@Map[Sort, unsorted, {2}];
     Fold[Cases, sorted, cnfPatt /. Or -> Alternatives]],
    {card, 1, Length@vars}]; // Timing
Length /@ pattTable