Mathematica Reduce/Solve:询问非重复值的最佳方式

Question

有几次我发现我有一个系统,我需要指定所有变量都有不同的值(即非重复).

我经常做这样的事情:

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]

其中Reduce等式的最后部分

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

要求不同的价值观.

有没有更好的方法来做到这一点？(我的意思是,不是产品等于零,而是指定I need all variables different)

Answer 1

从速度的角度来看,您在产品条件下会产生很大的开销.如果您的解决方案始终是数字,您可以生成所有解决方案,Reduce然后对其进行过滤 - 在某些情况下可能会更快.例如,在手头的情况下:

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]

你可以进行后期处理,例如这样(也许不是最好的方法):

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}

至少对于这种特殊情况,它要快得多.

Answer 2

对于小问题,post =处理以删除不需要的解决方案可能是最好的.对于较大的问题,至少有两种有用的方法.

(1)如果允许的值是连续的,或几乎是连续的,则可以为每个原始变量的网格和可能的值创建0-1变量.例如,如果您的变量旨在填写标准的Sudoku数组,则可以使用x [i,j,k] = 1来指示第i行col j中的值为k.例如,行1中没有值重复的约束将是

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

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

如果并非所有值都需要在所有位置(例如行)中使用,则可以将这些值变为不等式.

(2)另一种方法是,如果需要区分的值,则为每对使用0-1变量.我们假设值范围至少有一个已知的上限和下限.叫它m.因此,对于任何变量x和y,我们知道差异在-m和m之间(可以在那里加/减,但不是必需的).

对于需要不同的x [i]和x [j]对,添加一个新变量0-1 k [i,j].想法是如果x [i]> x [j]则需要为1,如果x [j]> x [i]则需要为0.*

对于这一对,我们添加两个方程.我将以非扩展形式显示它们,因为这可能稍微容易理解.

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

如果x [i]> x [j]则两者仅满足k [i,j] == 1.反之亦然x [j]> x [i]和k [ij] == 0.

当变量可以跨越显着大于变量数量的值范围时,或者当所有对被约束为不同值的情况少得多时,这可能是首选方法.

Daniel Lichtblau

*周六晚上很晚,所以我倒退了.另外,请你修复所有拼写错误.