1
$\begingroup$

General problem

Given a set of logical expressions I need to find numbers with a margin between pairs that obey the logical rules.

Example

For the expression $m=n=o,p=q$ with a margin of 10 the following (m,n,o,p,q)-tuples would be valid:

(7,7,7,17,17)

(1,1,1,20,20)

as they obey all the rules and have at least 10 between tuples of identical items. For completeness the following tuples wouldn't be valid:

(1,2,2,20,20)

(1,1,1,9,9)

In the first one a logical expression is violated, in the second case the margin is too small.

Details and started minimal example

Assume we have many logical expressions of completely analytical form as in

((n == n && i == m) || (n == m && i == n)) && ((o == n && 
 i == i) || (o == i && i == n)).

I am absolutely aware of the fact that some of those expressions do not contain information (e.g., as in $n=n$). To eliminate those and to expand the expression to get individual cases I use LogicalExpand wrapped around such that

LogicalExpand[((n == n && i == m) || (n == m && i == n)) && ((o == n &&
   i == i) || (o == i && i == n))]
(* Out: (m == i && o == n) || (m == i && n == i && o == i) || (n == i && 
n == m && o == i) || (n == i && n == m && o == n)*).

For each of the Or-Arguments I need to find a specific tuple matching all criteria. The only way I can currently imagine is (not in code but paraphrased here) to choose the first letter in the alphabet in an Equal and to replace via ReplaceAll. But this seems error-prone and cumbersome. Is there a more elegant way?

$\endgroup$
  • 3
    $\begingroup$ FindInstance[]? $\endgroup$ – Feyre Feb 1 '17 at 20:00
  • $\begingroup$ @Feyre I did not know about this function, to be honest. Thanks for pointing it out. It works, of course, as expected but for sth. like FindInstance[(m == i && o == n && p != q), {m, n, o, i, p, q}, Integers] it returns {{m -> 0, n -> 0, o -> 0, i -> 0, p -> 0, q -> 2}} and with this it does not fulfill my criterion of the margin because I want everything considered to be different if not otherwise stated. {{m -> 0, n -> 10, o -> 10, i -> 0, p -> 20, q -> 30}} would be what I am looking for. $\endgroup$ – pbx Feb 1 '17 at 20:16
  • $\begingroup$ Well you have to give all the necessary conditions: FindInstance[{m == i && n == o && n - m > 9 && p - n > 9 && q - p > 9}, {i, m, n, o, p, q}] $\endgroup$ – Feyre Feb 1 '17 at 20:22
  • $\begingroup$ @Feyre I just upvoted your comment and will accept your answer if you prefer to not only answer my question in the comments but to make it a full answer. One last question, though: Wouldn't I again have the same problem to find the needed margin conditions as I had at the beginning? I need a representative of each group, right? $\endgroup$ – pbx Feb 1 '17 at 20:52
1
$\begingroup$

You seem to want to do all of this programmatically, this is possible, but not worth the effort unless you have to do this many times.

Suppose our boolean function is stored in set;

set = ((n == n && i == m) || (n == m && i == n)) && ((o == n && 
      i == i) || (o == i && i == n));

It is possible this gives multiple solutions, here we'll only treat the first one. We'll need to extract the variables we're using too.

If[Depth@set > 3, set = set[[1]]];
vars = {i ,m ,n ,o};

We now have the tools to solve any set of bools, all we need now is a programmatic way of introducing the margin:

margins = 
  Flatten[{Cases[set /. And -> List, a_ == b_][[All, 1]], 
    Cases[set /. And -> List, a_ != b_] /. Unequal -> List}];
margins = Greater @@ (margins + Table[9 (i - 1), {i, Length@margins}])

We can then run the FindInstance[], here I also make sure all values are positive:

FindInstance[Flatten[{set, margins, Thread[vars >= -1]}], vars]

{{i -> 0, m -> 0, n -> 10, o -> 10}}

You can turn the whole thing into a function:

boolfind[set_, vars_] := Module[{l, margins},
  l = Range@Length@set;
  If[Depth@set > 3, set = set[[1]]];
  margins = 
   Flatten[{Cases[set /. And -> List, a_ == b_][[All, 1]], 
     Cases[set /. And -> List, a_ != b_] /. Unequal -> List}];
  margins = 
   Greater @@ (margins + Table[9 (i - 1), {i, Length@margins}]);
  FindInstance[Flatten[{set, margins, Thread[vars > -1]}], vars, 
   Reals]]

and run it:

boolfind[m == n == o && p == q]

{{m -> 0, n -> 0, o -> 0, p -> 10, q -> 10}}

boolfind[m == n == o && p == q == x]

{{m -> 10, n -> 10, o -> 10, p -> 0, q -> 0, x -> 0}}

boolfind[(m == i && o == n && p != q && r != t), {i, m, n, o, p, q, r, t}]

{{i -> 50, m -> 50, n -> 40, o -> 40, p -> 30, q -> 20, r -> 10, t -> 0}}

There's some things this doesn't take care of, but the examples you've given work with this.

If you need to accept instances of a single unpaired variable, you need add this to margins, and remove these from the FindInstance[] expression:

boolfind[set_, vars_] := Module[{l, margins},
  l = Range@Length@set;
  If[Depth@set > 3, set = set[[1]]];
  margins = 
   Flatten[{Cases[set /. And -> List, a_ == b_][[All, 1]], 
     Cases[set /. And -> List, a_ != b_] /. Unequal -> List, 
     Select[set /. And -> List, Length[#] == 0 &]}];
  margins = 
   Greater @@ (margins + Table[9 (i - 1), {i, Length@margins}]);
  FindInstance[
   Flatten[{Select[set /. And -> List, Length[#] > 0 &], margins, 
     Thread[vars > -1]}], vars, Reals]]

Then it works:

boolfind[(m == i && o == n && p != q && r), {i, m, n, o, p, q, r}]

{{i -> 40, m -> 40, n -> 30, o -> 30, p -> 20, q -> 10, r -> 0}}

$\endgroup$
  • 1
    $\begingroup$ Great concept so far. I refrain from posting an answer to my own question as you did most (read: almost all) of the work and I only want to extend it (in case anyone has the same issue like me with expressions like $m=i, n=i$ for whom the above code doesn't work). Mapping this to a graph problem and replacing your first margin definition with First /@ EquivalenceClasses[set, vars]; for EquivalenceClasses[req_, vars_] := Module[{edges}, edges = List @@@ Cases[req, a_ == b_]; ConnectedComponents@Graph[vars, UndirectedEdge @@@ edges] ]; does the trick for me. $\endgroup$ – pbx Feb 2 '17 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.