Mathematica減少/解決：請求非重複值的最佳方法

幾次我發現我有一個系統，我需要指定所有變量都獲得不同的值（即不重複）。Mathematica減少/解決：請求非重複值的最佳方法

我平時做這樣的事情：

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}] && 
    [email protected](Sequence @@ (Subsets[k, {2}] /. {x_, y_} -> (x - y))) != 0, 
k, Integers]

其reduce方程式

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

的最後部分，詢問不同的值。

有沒有更好的方法來做到這一點？（我的意思是，不是產品等於零，而是指定I need all variables different）

來源

2011-05-28 Dr. belisarius

對於一些小問題，post =處理刪除不需要的解決方案可能是最好的。對於較大的問題，至少有兩種有用的方法。（1）如果允許的值是連續的，或者接近這樣，可以爲每個原始變量和可能值的網格創建0-1個變量。例如，如果你的變量是用來填充一個標準的Sudoku數組，那麼x [i，j，k] = 1可以用來表示第i行col j中的值是k。例如，在第1行，不重複值是

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

... 總和[X [1，J，9] == 1，{Ĵ，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 [i.j] == 0。

當變量可以跨越大於變量數量的值範圍時，或者當所有對被限制爲不同值時，這可能是首選方法。

丹尼爾Lichtblau

*這是星期六深夜，因此逆什麼我得到了倒退。同時請修正所有錯別字。

來源

2011-05-29 03:19:41

從速度的角度來看，您正在產生大量產品條件的開銷。如果您的解決方案始終是數字，則可以使用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}

至少在這個特定的情況下，它快得多。

來源

2011-05-28 00:43:35

@Leonid任何關於何時更快地包含條件以及何時進行後期處理的預感？ – 2011-05-28 02:06:36

@belisarius爲此，我需要知道Reduce是如何工作的。但在我看來，對於很多變數來說，產品狀況總是非常緩慢。我的猜測是'Reduce'會嘗試比最終解決方案更多的解決方案（即使沒有產品條件），並且每個解決方案都會測試產品條件。因此，使用後處理可能總是更快，*如果*所有解決方案都可以適應內存。如果你有任何方法可以解決可能的解決方案的數量上限，並且它不是非常巨大的，我會後處理。 – 2011-05-28 07:00:21

Belisarius的代碼在等待幾分鐘後沒有給我答案，而你的確做到了。 +1。但是，如果解決方案的總數很高，或許足以超過可用內存，那麼可以做什麼？ – 2011-05-28 15:28:47

爲什麼不直接提供唯一性約束？

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}] && [email protected] , k, 
    Integers]//Timing 

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

從粗略地看一眼你的約束時，大多數的唯一要求是自通過其他約束滿足和設置a≠b≠e修復所有剩餘。沒有必要測試一切。對於例如，

f = a + b⇒f ≠ a & f ≠ b
f = e + g⇒f ≠ e & f ≠ g
2f = d + e⇒f ≠ d∵f ≠ e⇒g ≠ d
c = g + dc ≠ g⇒& c ≠ d

等等......您可能可以詳細解決這個問題。

我明白這可能只是一個測試的例子，我沒有一個聰明而快速的一站式答案，你可以不用考慮問題就可以使用。

來源

2011-05-28 01:59:59 abcd

是的，這只是一個例子。我不想檢查方程是否已經與平等不相容（通常方程本身就是其他一些鈣的輸出）！ – 2011-05-28 02:04:34

@belisarius：是否有一種簡單的方法將'Reduce'的輸出作爲嵌套列表？例如，如果你運行上面第一個Leonid代碼塊，它會返回'{{1,1,4,3,1,2,1}，{1,2,5,4,2,3,1}， ...}' – abcd 2011-05-28 02:10:44

如果我理解你的問題，一個簡單的替換規則將會（在這種情況下） – 2011-05-28 02:13:48

Mathematica減少/解決：請求非重複值的最佳方法

回答

相關問題