统计数组中不同元素的数量

Question

我是对约束编程和Minizinc不熟悉的新手。 我试图解决这个不算太难的问题，但却一无所获。

我想要计算在一个数组中出现过的不同元素的数量： 这是我的数组声明：

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

我已经尝试做了这样的事情：

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

但显然我的数组是这种类型：array[int]of var opt int，而该函数array2set无法接受此类型。

有什么想法吗？

- Aldebert Lucie

Answer 1

可能有不同的方法可以采取，但与您尝试的方法类似的方法是将数组中不同元素的计数分为两个步骤：

1. 计算域中值的出现次数。
2. 计算出现次数高于零的次数。

我们可以使用全局global_cardinality约束来计算出现次数，然后在其结果上使用简单的计数约束。

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

请注意，这可能不是最适合您的模型的最佳代码。对于某些求解器，全局计数可能不够高效。同样地，如果您的stopCountLeft包含变量，那么这意味着您正在创建一个可选变量数组，并且全局基数可能未定义为可选变量。

相反，我们可以编写一个蕴涵图。思路仍然相同，但是我们只使用布尔值来表示值是否正在使用，而不是计算值出现的次数。

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

请注意，这种方法的问题在于forall循环中发布的推论数量呈指数级增长。不过，我认为，由于影响很小，它应该表现得相当不错。

- Dekker1

Answer 2

在 MiniZinc 2.5.0 中，您可以这样做：

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

- Axel Kemper