Minizinc:计算与初始输出数组相关联的数组中不同变量的数量

Question

我试图计算数组中的出现次数，这些次数首先受到数组中相同值的约束，然后受到相关数组中不同变量的数量的约束。

我从这个型号的开始

set of int: OPTS = 1..4;
set of int: ASSIGN = 1..12;
array[ASSIGN] of var OPTS: result;

可以生成结果[ 1,2,1,3,3,4,1,3,1,1,2,4 ]

并希望与这些语句结合使用

enum CONDS = {A,B,C,D};
array[ASSIGN] of CONDS : const = [A,A,A,B,B,B,C,C,C,D,D,D];
array[OPTS] of var 0..max(CONDS): result2;
output ["(result) (result2)"]

并产生计数每个CCD_ 3 出现多少不同CCD_

[ 1,2,1,3,3,4,1,3,1,1,2,4 ] [3,2,2,2]

这意味着OPTS[1]与A、C和D中的至少一个相关，OPTS[2]有As和Ds，OPTS[3]有Bs和Cs，OPTS[4]有Cs和Ds。我对这个和以前的问题有点困惑，无法确定是考虑创建一个不太复杂的约束，还是一个更复杂的约束。我可能错过了一个简单的技巧。。。或者可能不那么明显？

我很想知道为什么当X = j时，我对以下内容的尝试不令人满意，当X = 1时，[0,0,3,0]和当X = i时，"[0,0,0]'"(这对我来说很有意义，但很明显，我不知道这个位置"X"应该如何与其他位置一起工作(。

constraint forall(i in OPTS, j in CONDS)(
result2[i] = 
count([ k == j / result[k] = i | k in const],X)
);

Answer 1

这里有一个模型可以解决您最初的问题。构造card({const[i] | i in ASSIGN where result[i]=o} )，使用集合理解{....}计算OPTS的不同值的数量，使用card(集合的基数(进行计数。

include "globals.mzn";
set of int: OPTS = 1..4;
set of int: ASSIGN = 1..12;
array[ASSIGN] of var OPTS: result = [1,2,1,3,3,4,1,3,1,1,2,4];
enum CONDS = {A,B,C,D};
array[ASSIGN] of CONDS : const = [A,A,A,B,B,B,C,C,C,D,D,D];
array[OPTS] of var 0..max(ASSIGN): result2;
solve satisfy;
constraint 
forall(o in OPTS) (
% count the number of different CONDS for this OPTS value o
result2[o] = card({const[i]  | i in ASSIGN where result[i]=o} )
)
;
output [
"result:(result)n",
"result2:(result2)n",
];

解决方案是

result:[1, 2, 1, 3, 3, 4, 1, 3, 1, 1, 2, 4]
result2:[3, 2, 2, 2]

更新：回答附加问题

你问为什么这个约束不能给出正确的答案：

constraint forall(i in OPTS, j in CONDS)(
result2[i] = 
count([ k == j / result[k] = i | k in const],X)
);

以下是这种方法的一些问题。

首先，我应该说，这种循环通常可能是一种很好的方法，但问题陈述要求我们计算不同区块的数量(如果每个区块包含许多值(，而不是所有出现的次数。

1. k in const循环通过所有值A,A,A,B,B,...(而不是索引(，这意味着result[k]被解释为result[A] ... result[D]，然后被翻译为result[1] ... result[4](A=1，B=2，C=3，D=4(，这不是您想要的。

   相反，k应该循环通过ASSIGN，而不是普通的k应该是CONDS0。

2. 另一个问题是对每个j in CONDS评估result2[i]；重复计数"；这几乎总是意味着麻烦。(还要注意，在约束编程中，值永远不会更新。如果一个循环中results[i]中有一个值，而另一个循环则有另一个值。则模型为UNSAT。(

   相反，应该使用嵌套循环：

constraint
forall(i in OPTS) (
forall(j in CONDS) (
% ...
)
);

3. 但是，使用count(或sum(意味着要计算所有CONDS的出现，例如对于值1，此计数两个CCD_ 28(来自第一块(，这是不正确的

要修复此问题，只需计算CONDS的一次出现次数。在上面的模型中，我使用集合方法。这里有另一种方法，使用OPTS0，它只计算每个匹配的CONDS值中的一个。

constraint 
forall(o in OPTS) (
result2[o] = sum(c in CONDS) (
exists(k in ASSIGN) ( const[k] = c / result[k] = o)
)
)
;