Mathematica Reduce/Solve: лучший способ задать не повторяющиеся значения

Ответ 1

Для небольших проблем 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]. Идея в том, что она должна быть 1, если x [i] > x [j] и 0, если x [j] > x [i]. *

Для этой пары добавим два уравнения. Я покажу их в нерасширенной форме, поскольку это может быть немного легче понять.

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.

Это может быть предпочтительным методом, когда переменные могут охватывать диапазон значений, существенно больших, чем число переменных, или когда намного меньше, чтобы все пары были ограничены как отдельные значения.

Даниэль Лихтблау

* Это в субботу вечером, поэтому отмените все, что я получил назад. Также, пожалуйста, исправьте все опечатки, пока вы на нем.

Ответ 2

С точки зрения скорости вы вызываете большие накладные расходы с этим условием продукта. Если ваши решения всегда являются числами, вы можете создавать все решения с помощью 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}

По крайней мере, для этого конкретного случая это было намного быстрее.

Ответ 3

Почему бы не поставить ограничение уникальности напрямую?

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 + d ⇒ c ≠ g и c ≠ d

и т.д. Возможно, вы можете подробно разобраться в этом.

Я понимаю, что это, вероятно, всего лишь тестовый пример, и у меня нет умного и быстрого ответа на один вопрос, который вы можете использовать, не задумываясь о проблеме.