Mathematica Reduce/Solve: Best way to ask for non-repeating values

A few times I found I had a system and I need to specify that all variables get different values (ie non-repeating).

I usually do things like this:

k = {a, b, c, d, e, f, g}; 
开发者_如何学运维Reduce[
   a != 2 && f == a + b && g == c - d && f == (d + e)/2 && f == e + g &&
   First[And @@@ {0 < # < 8 & /@ k}] && 
   Times@(Sequence @@ (Subsets[k, {2}] /. {x_, y_} -> (x - y))) != 0, 
k, Integers]

Where the last part of the Reduce equation

Times@(Sequence @@ (Subsets[k, {2}] /. {x_, y_} -> (x - y))) != 0

asks for different values.

Are there better ways to do this? (I mean, not the product equal zero, but to specify I need all variables different)

---

From the speed viewpoint, you are inducing a large overhead with that product condition. If your solutions are always numbers, you can produce all solutions with Reduce and then filter them - it may be faster in some cases. For example, in the case at hand:

k = {a, b, c, d, e, f, g};
sl = Reduce[ a != 2 && f == a + b && g == c - d && f == (d + e)/2 && f == e + g &&
      First[And @@@ {0 < # < 8 & /@ k}], k, Integers]

You can do the post-processing, for example like this (perhaps not the best way):

In[21]:= Select[{#, First[k /. Solve[#, k]]} & /@ List @@ sl, 
            MatchQ[Tally[#[[2]], Equal][[All, 2]], {1 ..}] &][[All, 1]]

Out[21]= {a == 3 && b == 2 && c == 7 && d == 6 && e == 4 && f == 5 && g == 1}

At least for this particular case, it was much faster.

---

For smallish problems, post=processing to remove unwanted solutions might be best. For larger problems there are at least two useful approaches.

(1) If the allowed values are say contiguous, or nearly so, could create 0-1 variables for the grid of each original variable and possible value. For example, if your variables are intended to fill out a standard Sudoku array, then x[i,j,k]=1 could be used to indicate that the value in row i, col j, is k. The constraints that e.g. no value in row 1 is repeated would be

Sum[x[1,j,1]==1, {j,9}]

... Sum[x[1,j,9]==1, {j,9}]

If not all values need to be used in all places (e.g. rows) then these could be made into inequalities instead.

(2) Another approach is to use 0-1 variables for each pair if values that needs to be distinct. We assume there is at least a known upper and lower bound on value ranges. Call it m. So for any pair of variables x and y we know that the difference is between -m and m (could add/subtract ones there, but not essential).

For the pair x[i] and x[j] that need to be distinct, add a new variable 0-1 k[i,j]. The idea is it will need to be 1 if x[i]>x[j] and 0 if x[j]>x[i].*

For this pair we add two equations. I will show them in non-expanded form as that might be slightly easier to understand.

x[i]-x[j] >= k[i,j] + m*(k[i,j]-1)
x[j]-x[i] >= (1-k[i,j]) + m*(-k[i,j])

If x[i]>x[j] then both are satisfied only for k[i,j]==1. Vice versa for x[j]>x[i] and k[i.j]==0.

This might be the preferred method when variables can span a range of values substantially larger than the number of variables, or when far fewer that all pairs are constrained to be distinct values.

Daniel Lichtblau

*It's late Saturday night, so reverse anything I got backwards. Also please fix all typos while you are at it.

---

Why not supply a uniqueness constraint directly?

k = {a, b, c, d, e, f, g};
uniqueness = {a != b != e};
sl = Reduce[
  a != 2 && f == a + b && g == c - d && f == (d + e)/2 && f == e + g &&
    First[And @@@ {0 < # < 8 & /@ k}] && First@uniqueness , k, 
  Integers]//Timing

Out[1]= {0.046791, a == 3 && b == 2 && c == 7 && d == 6 && e == 4 && f == 5 && g == 1}

From a cursory glance at your constraints above, most of the uniqueness requirements are self satisfied by the other constraints and setting a≠b≠e fixes all the remaining. There is no need to test for everything. For e.g.,

1. f = a + b ⇒ f ≠ a & f ≠ b
2. f = e + g ⇒ f ≠ e & f ≠ g
3. 2f = d + e ⇒ f ≠ d ∵ f ≠ e ⇒ g ≠ d
4. c = g + d ⇒ c ≠ g & c ≠ d

and so on... You can probably work that out in detail.

I understand this is probably just a test example, and I don't have a smart and fast one stop answer that you can use without thinking about the problem.