Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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!

share|improve this question
    
    
@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. :-) –  Felix Kasza Feb 2 at 11:06
    
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) –  Mr.Wizard Feb 2 at 11:13
3  
FindInstance went with a heuristic method choice that was far from optimal. Next version should be better.. –  Daniel Lichtblau Feb 6 at 14:43
2  
@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. –  Daniel Lichtblau Feb 7 at 15:22

4 Answers 4

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.

share|improve this answer
    
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.) –  Mr.Wizard Feb 10 at 13:46

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?

share|improve this answer
    
Too long for a comment, I'll try amending the original post ... –  Felix Kasza Feb 7 at 12:47

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]]
share|improve this answer
1  
I don't think FindInstance uses assumptions; if so, this would be equivalent to the OP's first example. –  Michael E2 Feb 7 at 0:19

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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