Minizinc: Pairwise intersection of int arrays

Question

I have some arrays (can be more than 10) of int variables. I am looking for an efficient way to constraint the pairwise intersection count of these arrays, i.e that each array cannot have more than x elements in common with any other array.

Example in pseudocode: [1,4,4] and [2,2,1] would have one element in common -> the number 1. [4,4,4] and [9,4,4] have the element 4 in common, the duplicate 4 should be ignored.

In my current implementation, I iterate over all pairs of arrays and for each par check for each element if it is in the other array as well. This is of course very slow and the duplicates are not eliminated as they should be.

The interesting part of my code looks like this:

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;

I have thought about using minizinc sets as they support some set operations, but I could not get them to work with variables.

Any ideas?

Answer 1

Perhaps something like this, using array2set for converting the arrays to sets and then card and intersect to calculate the number of intersections between each pair.

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 
];

The output of this model is

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