Minizinc：根据与第二个数组的匹配计算数组中的出现次数，以二维数组输出

Question

我遇到的下一堵墙是尝试计算一个数组中出现的次数，条件是它们与另一个数组中的值匹配。

我想合并以下模型

set of int: OPTS = 1..4;
set of int: ASSIGN = 1..12;

array[ASSIGN] of var OPTS: result;

这些陈述

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,CONDS] of var int: result2;

output ["\(result) \(show2d(result2))"]

并生成一个输出，计算每个 OPTS 每个 CONDS 出现的次数，例如

[ 1,2,1,3,3,4,1,3,1,2,2,4 ] [|2,0,2,0|1,0,0,2|0,2,1,0|0,1,0,1]

即OPTS[1]有2个ACONDS、0个BCONDS和2个CCONDS和0个DCONDS，而OPTS[2]有1个ACONDS、0个BCONDS、0个CCONDS和2个DCONDS，依此类推。

我不知道我经历了多少以下组合，但其中 none 产生了预期的结果，尽管我认为应该是合乎逻辑的。

constraint forall(i in OPTS,j in CONDS)(
     result2[i,j] = 
       sum(k in result)(% tried all sorts of things here with i,j, and k and if statements)
);

Answer 1

这是一个模型，针对 OPTS 中的每个值计算 CONDS 中出现的次数。棘手的部分是 count 构造，其中必须检查 result 中的值是否是 OPTS 值 o。这是用count约束完成的，其中(result[i]==0)是条件result[i]中的这个值是我们想要的o，然后我们检查COND它是什么属于 (const[i]).

include "globals.mzn";

set of int: OPTS = 1..4;
set of int: ASSIGN = 1..12;

% Note: hard coded with the example from the question.
array[ASSIGN] of var OPTS: result = [ 1,2,1,3,3,4,1,3,1,2,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];

% count the number of occurences in each chunk
array[OPTS,CONDS] of var 0..max(ASSIGN): result2;

constraint 
   % for each integer in OPTS
   %     count the number of occurrences of each c in CONDS
   forall(o in OPTS) (
       forall(c in CONDS) (
           result2[o,c] = count([const[i]*(result[i] == o) | i in ASSIGN],c)
       )
   )
;

solve satisfy;

output [
    "const: \(const)\n",
    "result: \(result)\n",
    "result2: ", show2d(result2), "\n",
];

您示例中带有硬编码 result 的模型的输出是：

const: [A, A, A, B, B, B, C, C, C, D, D, D]
result: [1, 2, 1, 3, 3, 4, 1, 3, 1, 2, 2, 4]
result2: [| 2, 0, 2, 0 |
   1, 0, 0, 2 |
   0, 2, 1, 0 |
   0, 1, 0, 1 |]

编辑： 可以使用全局约束代替计数循环，这应该更有效 global_cardinality。它使用与 count 版本相同的想法，但包装在一个 forall 循环中：

constraint 
   forall(o in OPTS) (
       global_cardinality([const[i]*(result[i] == o) | i in ASSIGN],OPTS,result2[o,..])
   )
;

Minizinc：根据与第二个数组的匹配计算数组中的出现次数，以二维数组输出

Minizinc: counting occurrences in an array based on matches to a second array, outputting in 2d array

arrays

minizinc