Count the number of different elements in an array

Question

I am new to constraint programming and to Minizinc. I have look for a solution to this not relly hard task but I found nothing.

I want to count the number of different elements that appear in an array: This is the declaration of my array:

array[1..n,1..n] of var 1..n: countLeft;
  

I have try to do like this:

constraint 
   forall(j in 1..n) (
        length(array2set([countLeft[i,j]|i in 1..stopCountLeft[j]]) )==left_vision[j]
        );

But apparently my array is of type: array[int]of var opt int and is not accept by the function array2set.

Any ideas?

Answer 1

There might be different approaches you could take, but an approach that is similar to what you try would be to split the counting of different elements in an array into two steps:

1. Counting the occurrence of the values in the domain.
2. Counting the amount of times the occurrence is higher than zero.

We can use the global global_cardinality constraint to count the occurrences and then use a simply count constraint over its result.

include "global_cardinality_fn";

array[1..n] of var int: occurrences = global_cardinality(YOURARRAY, [i | i in 1..n]);

var int: num_diff = count(o in occurrences) (o > 0);

Note, however, that this might not be the best code for your model. For some solvers global_cardinality might not be perform well enough. Similarly if your stopCountLeft contains variables, then that means that you are creating a array of optional variables, and global_cardinality might not be defined for optional variables.

Instead we can write an implication graph instead. The idea is still the same, but instead of counting the number of a value occurring, we just use a boolean value to signal wether the value is in use.

array[1..n] of var bool: occurs;

constraint forall(i,j in 1..n) (YOURARRAY[i] = j -> occurs[j]);

var int: num_diff = count(occurs);

Note that the problem with this approach is the exponential number of implications posted in the forall loop. However, I suspect that, with implications being small, it would perform reasonably well.

Answer 2

In MiniZinc 2.5.0, you can do something like this:

array[int, int] of int: a = 
  [| 1, 1,
   | 2, 3, 
   | 3, 4 |];

set of int: Rows = index_set_1of2(a);
set of int: Cols = index_set_2of2(a);

int: values = card({ a[r, c] | r in Rows, c in Cols });

output ["\(values) values in "] ++ 
       [if c == 1 then "\n" else "" endif ++ 
        "\(a[r, c]) " | r in Rows, c in Cols];