Minizinc：int 数组的成对交集

Question

我有一些 int 变量数组（可以超过 10 个）。我正在寻找一种有效的方法来限制这些数组的成对交集计数，即每个数组与任何其他数组的共同元素不能超过 x 个。

伪代码示例：[1,4,4] 和 [2,2,1] 将有一个共同元素 -> 数字 1。 [4,4,4] 和 [9,4,4] ]有共同的元素4，重复的4应该忽略。

在我当前的实现中，我遍历所有数组对，并为每个 par 检查每个元素是否也在另一个数组中。这当然很慢，并且没有按应有的方式消除重复项。

我的代码中有趣的部分如下所示：

constraint matches [0] = exists ( i in index_set(values1) ) ( values1[i]==values2[0] );
constraint matches [1] = exists ( i in index_set(values1) ) ( values1[i]==values2[1] );
constraint matches [2] = exists ( i in index_set(values1) ) ( values1[i]==values2[2] );
constraint matches [3] = exists ( i in index_set(values1) ) ( values1[i]==values2[3] );
constraint matches [4] = exists ( i in index_set(values1) ) ( values1[i]==values2[4] );

constraint sum(matches) <  x;

我考虑过使用 minizinc 集合，因为它们支持一些集合操作，但我无法让它们使用变量。

有什么想法吗？

Answer 1

也许是这样的，使用 array2set 将数组转换为集合，然后 card 和 intersect 计算每对之间的交集数。

int: rows = 4; % number of columns
int: cols = 5; % number of rows
array[1..rows,1..cols] of int: a = array2d(1..rows,1..cols, 
               [
               4,6,9,5,6,
               5,3,7,1,3,
               3,8,3,3,1,
               1,1,4,7,2,
               ]);
% convert the arrays to sets
array[1..rows] of set of int: s = [array2set([a[i,j] | j in 1..cols]) | i in 1..rows];

% decision variables
var int: z;

solve satisfy;
constraint
    z = sum(r1,r2 in 1..rows where r1 < r2) (
              card(s[r1] intersect s[r2])
        )
;
output 
[
  "z:\(z)\n"
] ++
[
  show(s[i]) ++ "\n"
  | i in 1..rows 
];

这个模型的输出是

z:7
{4,5,6,9}
{1,3,5,7}
{1,3,8}
{1,2,4,7}

Minizinc：int 数组的成对交集

Minizinc: Pairwise intersection of int arrays

intersection

constraint-programming

minizinc