Проверка элементов в массиве MiniZin c - PullRequest
Новая
       18

Проверка элементов в массиве MiniZin c

2 голосов
/ 06 февраля 2020

Я хочу создать два массива в MiniZin c с одинаковыми предметами, необязательно в том же порядке. Здесь каждый элемент в A0 также должен быть в A1: 

array[1..3] of var int:A0;
array[1..3] of var int:A1;

constraint forall(A2 in A0)(
  (A2 in A1) /\ A2 < 5
 );

Но здесь, похоже, есть ошибка типа: 

MiniZinc: type error: type error in operator application for `'in''. No matching operator found with left-hand side type `var int' and right-hand side type `array[int] of var int'

Как это возможно проверить, содержит ли массив тот же элемент, что и в другом массиве?

1 Ответ

2 голосов
/ 06 февраля 2020

Редактировать : в файле builtins.mzn есть array2set, но он не задокументирован в https://www.minizinc.org/doc-2.4.2/.

Следующая модель работает для большинства решателей FlatZin c, таких как Gecode, Google-OR-tools, Choco, PicatSAT и JaCoP, но не для Chuffed (см. Ниже). Обратите внимание на включение «nosets.mzn», так что решатели без встроенной поддержки для установленных переменных могут запускать модель. Кроме того, я добавил меньший домен A0 и A1 для упрощения тестирования. 

include "nosets.mzn"; % Support for set variables for all solvers
array[1..3] of var 0..10: A0;
array[1..3] of var 0..10: A1;

constraint
   forall(A2 in A0)( 
     A2 in array2set(A1) /\ A2 < 5
   )
   /\
   forall(A2 in A1)(
     A2 in array2set(A0) /\ A2 < 5
   );

   solve satisfy;

   output [ "A0: \(A0) A1: \(A1)\n" ];

Однако некоторым решателям это не нравится:

  • Chuffed: Throws «Ошибка: Реестр: ограничение bool_lin_eq не найдено в строке № 101»

Даже позднее примечание : если доменом является var int (вместо моего var 0..10), то MiniZin c квакает со странной (и длинной) ошибкой: 

...
in array comprehension expression
  comprehension iterates over an infinite set

Так что array2set требует, чтобы переменные домены были ограничены.

Это первый ответ Вот подход, который, кажется, работает, то есть использование exists и проверка на равенство элементов: 

constraint forall(A2 in A0)(
              exists(i in 1..3) ( A2 = A1[i] /\ A2 < 5)
);

Примечание: Это ограничение только гарантирует, что элементы в A0 находятся в A1. Таким образом, в A1 могут быть элементы, которых нет в A0. Например,

A0: [1,1,4]

A1: [1,4,3]

Я полагаю, что вы также хотите обратное, то есть все элементы в A1 также находится в A0: 

constraint forall(A2 in A1) (
   exists(i in 1..3) ( A2 = A0[i] /\ A2 < 5)
);

Примечание: следующие НЕ работают, но было бы неплохо иметь их. Оба выдают ошибку MiniZinc: internal error: var set comprehensions not supported yet. 

% idea 1
constraint forall(A2 in A0)(
   A2 in {A1[i] | i in 1..3} /\ A2 < 5
);

% idea 2
constraint forall(A2 in A0) (
     A2 in {a | a in A1} /\ A2 < 5         
);
...