arrays - 在 Minizinc 中计算数组中出现频率最高的元素

解决这个问题的“经典”方法是将全局约束global_cardinality与max.

以下是使用这些约束对这个问题进行建模的一种方法；它还显示最频繁的数字。

使用这种方法的缺点是必须创建一个新数组gcc（用于“全局基数”），其中包括每个数字的出现次数0..upb（upb数组的上限在哪里a），如果数组中有大量数字。此外，必须对索引有点小心，例如不要忘记在gcc.

这种方法的优点——除此之外可以在求解器中高效实现——可以在gcc数组上添加一些额外的约束：这里我添加了显示最频繁的数字的功能（使用arg_max(a)）；它可能不止一个这样的数字，然后会给出多种解决方案。

include "globals.mzn";   

int: n = 7;
array[1..n] of int: a = [15, 14, 39, 23, 14, 14, 8];
% array[1..n] of var 0..29: a; % using decision variables

% upper value of a
int: upb = ub_array(a);

% Number of occurrences in a
array[0..upb] of var 0..n: gcc;

% max number of occurrenes
var 0..upb: z = max(gcc);

% The value of the max number of occurrences
var 0..upb: max_val = arg_max(gcc)-1;

solve satisfy;

constraint
    % count the number of occurrences in a
    global_cardinality(a, array1d(0..upb,[i | i in 0..upb]), gcc)
;

output [
    "a: \(a)\n",
    "upb: \(upb)\n",
    "gcc: \(gcc)\n",
    "z: \(z)\n",
    "max_val: \(max_val)\n",        
    "ub_array(a): \(lb_array(a))..\(ub_array(a))\n",
  ];

这是该模型的输出：

a: [15, 14, 39, 23, 14, 14, 8]
upb: 39
gcc: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
z: 3
max_val: 14
ub_array(a): 8..39
----------
==========

arrays - 在 Minizinc 中计算数组中出现频率最高的元素

问题描述

解决方案

推荐阅读