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)"]

并生成一个输出，计算每个 OPTS

出现的不同 CONDS 的数量

[ 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、[0,0,3,0] 当 X = 1 和 '[0,0,0,0]' 当 X = i（这对我来说很有意义，但显然我不知道这个位置 '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)
);

这种方法存在一些问题。

首先我要说的是这种循环一般来说可能是一个很好的方法，但是问题陈述要求我们计算 不同块的数量 （每个块包含许多值），而不是所有出现的次数。

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 应该是 conds[k].
另一个问题是每个 j in CONDS 都会计算 result2[i]，即它会进行“重复计算”，这几乎总是意味着麻烦。（另请注意，在约束编程中，值永远不会更新。如果一个循环在 results[i] 中得到一个值，而在另一个循环中得到另一个值，则该模型是 UNSAT。）

应该使用嵌套循环：

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

但是，使用 count（或 sum）意味着您计算所有 CONDS 的出现次数，例如对于价值 1 这很重要两个 A（来自第一个块）不正确。

要解决这个问题，只需计算 CONDS 出现一次即可。在上面的模型中，我使用了集合方法。这是另一种方法，使用 exists 只计算每个匹配的 CONDS 值中的一个。

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

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

Minizinc: counting number of different variables in array associated with initial output array

arrays

constraints

minizinc