8
$\begingroup$

I took a quick look for FindInstance and Solve-related questions but came up empty for the aspect that I am curious about. So here is my newbie question:

FindInstance[{ s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0 },{s,e,n,d,m,o,r,y},Integers]

runs as quickly as one would expect. But

FindInstance[{ s!=e!=n!=d!=m!=o!=r!=y, s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0 },{s,e,n,d,m,o,r,y},Integers]

takes ages -- long enough that I ran out of patience before MMA was done.

And now I am curious: Why would Mathematica suddenly display less maths ability than a third-grader?

bill_s suggested something much faster, but it is not equivalent to the original problem. The original inequality required all variable values to be different from all other variable values, such that each value can only be used for one variable. The FindInstance statement in Bill's post only compares x[i] to the ith value, but not to the other n-1 values.

In other news,

FindInstance[{ (*s!=e,s!=n,s!=d,s!=m,s!=o,s!=r,s!=y,*) (*e!=n,e!=d,e!=m,e!=o,e!=r,e!=y,*) n!=d,n!=m,n!=o,n!=r,n!=y, d!=m,d!=o,d!=r,d!=y, m!=o,m!=r,m!=y, o!=r,o!=y, r!=y, s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0 },{s,e,n,d,m,o,r,y},Integers]

~1.1 seconds (on my laptop).

FindInstance[{ (*s!=e,s!=n,s!=d,s!=m,s!=o,s!=r,s!=y,*) e!=n,e!=d,e!=m,e!=o,e!=r,e!=y, n!=d,n!=m,n!=o,n!=r,n!=y, d!=m,d!=o,d!=r,d!=y, m!=o,m!=r,m!=y, o!=r,o!=y, r!=y, s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0 },{s,e,n,d,m,o,r,y},Integers]

2nd comment uncommentd. ~20 s.

FindInstance[{ s!=e,s!=n,s!=d,s!=m,s!=o,s!=r,s!=y, e!=n,e!=d,e!=m,e!=o,e!=r,e!=y, n!=d,n!=m,n!=o,n!=r,n!=y, d!=m,d!=o,d!=r,d!=y, m!=o,m!=r,m!=y, o!=r,o!=y, r!=y, s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0 },{s,e,n,d,m,o,r,y},Integers]

Both comments uncommented. ~1 minute.

The original version (multiple inequalities in one condition):

Timing[FindInstance[{ s!=e!=n!=d!=m!=o!=r!=y, s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0}, {s,e,n,d,m,o,r,y},Integers]]

150 seconds!

Improve this question
$\endgroup$
12
  • $\begingroup$ Related: FindInstance with a Diophantine equation seems to go on forever $\endgroup$ Commented Feb 2, 2014 at 10:48
  • $\begingroup$ @Mr.Wizard Thanks, that was one of the questions I came across, and there, at least, MMA had the excuse of actually having to do a little bit of work. :-) $\endgroup$ Commented Feb 2, 2014 at 11:06
  • $\begingroup$ Okay, I didn't know if you had seen it. I agree that the behavior you illustrate is enigmatic, and I don't have an explanation for it. In this particular case you could use Reduce @ {s != e != n != d != m != o != r != y, s == 9, r == 8, d == 7, n == 6, e == 5, y == 2, m == 1, o == 0} to remove the inequalities, but this operation itself takes much longer than it arguably should. I would have expected both of your examples to be either fast or slow, rather than one of each. (continued) $\endgroup$ Commented Feb 2, 2014 at 11:13
  • 4
    $\begingroup$ FindInstance went with a heuristic method choice that was far from optimal. Next version should be better.. $\endgroup$ Commented Feb 6, 2014 at 14:43
  • 2
    $\begingroup$ @Felix What you wrote is clear in English. As for the reason, I believe the number of explicit inequalities figures into the method choice heuristic so that could be the cause of worse-than-linear complexity. $\endgroup$ Commented Feb 7, 2014 at 15:22

5 Answers 5

Reset to default
4
$\begingroup$

No one has upgraded this post in a long time and as Danny promised all the problems the OP posted have been dealt with. In v 11.1 for instance, the last one now runs in a lot less than 150 seconds.

Timing[FindInstance[{ s!=e!=n!=d!=m!=o!=r!=y, s==9,r==8,d==7,n==6,e==5,y==2,m==1,o==0}, {s,e,n,d,m,o,r,y},Integers]] {0.01, {{s -> 9, e -> 5, n -> 6, d -> 7, m -> 1, o -> 0, r -> 8, y -> 2}}}
Improve this answer
$\endgroup$
4
+50
$\begingroup$

In the comments, Daniel Lichtblau wrote:

[...] I believe the number of explicit inequalities figures into the method choice heuristic so that could be the cause of worse-than-linear complexity.

So it would seem that FindInstance made an unfortunate choice in tackling this, admittedly odd, set of inequalities.

One possible work-around would be to use smaller, non-overlapping, subsets of inequalities: a!=b!=c!=d&&e!=f!=g!=h and to filter the solution set returned by FindInstance.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ There is no provision for marking a comment as an answer. If after encouraging the comment's author to post it as an answer he does not, it is entirely appropriate to make it into an answer yourself as you did here. (Though I would copy the comment verbatim.) $\endgroup$ Commented Feb 10, 2014 at 13:46
2
$\begingroup$

This is more of an extended comment than a genuine answer... but consider this generalization of the problem:

n = 10; xVec = Array[x, n]; vals = RandomInteger[{0, 10}, n]; FindInstance[Thread[xVec == vals], xVec] FindInstance[Thread[xVec != vals], xVec] Flatten[{Thread[xVec[[1 ;; n/2]] != vals[[1 ;; n/2]]], Thread[xVec[[n/2 + 1 ;; n]] == vals[[n/2 + 1 ;; n]]]}] {{x[1] -> 10, x[2] -> 7, x[3] -> 5, x[4] -> 4, x[5] -> 4, x[6] -> 8, x[7] -> 5, x[8] -> 0, x[9] -> 3, x[10] -> 3}} {{x[1] -> 0, x[2] -> 0, x[3] -> 0, x[4] -> 0, x[5] -> 0, x[6] -> 0, x[7] -> 0, x[8] -> 1, x[9] -> 0, x[10] -> 0}} {x[1] != 7, x[2] != 2, x[3] != 2, x[4] != 2, x[5] != 3, x[6] == 3, x[7] == 6, x[8] == 5, x[9] == 1, x[10] == 6}

Moreover, it works quite well for even large size problems:

n = 500; xVec = Array[x, n]; vals = RandomInteger[{0, 10}, n]; First[FindInstance[Thread[xVec == vals], xVec] // Timing] First[FindInstance[Thread[xVec != vals], xVec] // Timing] First[Flatten[{Thread[xVec[[1 ;; n/2]] != vals[[1 ;; n/2]]], Thread[xVec[[n/2 + 1 ;; n]] == vals[[n/2 + 1 ;; n]]]}] // Timing] 2.449844 0.911796 0.000378

Why is the last one so fast compared to the others? It doesn't matter if you rearrange the orders of the three tests. Maybe the slowness has to do with the specific variable names and/or values chosen?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Too long for a comment, I'll try amending the original post ... $\endgroup$ Commented Feb 7, 2014 at 12:47
1
$\begingroup$

I am not sure why it takes long time, however, this works quite fast.

Assuming[s != e != n != d != m != o != r != y, FindInstance[{s == 9, r == 8, d == 7, n == 6, e == 5, y == 2, m == 1, o == 0}, {s, e, n, d, m, o, r, y}, Integers]]
Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I don't think FindInstance uses assumptions; if so, this would be equivalent to the OP's first example. $\endgroup$ Commented Feb 7, 2014 at 0:19
1
$\begingroup$

The following is just my guess. Usually != is not dealt with directly, it is broken into a<b || a>b. Then it's natural that the number of cases grows exponentially.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.