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

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 接受。

有任何想法吗？

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

但请注意，这可能不是最适合您的模型的代码。对于某些求解器来说global_cardinality可能性能不够好。同样，如果您stopCountLeft包含变量，则意味着您正在创建可选变量的数组，并且global_cardinality可能不会为可选变量定义。

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

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。然而，我怀疑，在影响很小的情况下，它的表现会相当好。