请求编写MiniZinc函数计算数组第n大值

需求说明 #

需要编写MiniZinc代码来计算给定数组中的第n大值，示例输入如下：

array[1..10] of 1..200 : t=[30,20,30,40,50,50,70,10,90,100];
var int : nth_largest;

实现代码 #

以下是通过约束定义实现的完整代码，可直接运行得到结果：

array[1..10] of 1..200 : t=[30,20,30,40,50,50,70,10,90,100];
int: n = 3; % 指定要查找的第n大值，可按需修改
var int : nth_largest;

% 辅助数组，标记每个元素是否大于等于目标值
array[1..10] of var bool: is_ge;

constraint forall(i in 1..10) (is_ge[i] = (t[i] >= nth_largest));
% 至少有n个元素大于等于目标值
constraint sum(is_ge) >= n;
% 最多有n-1个元素大于目标值
constraint sum([t[i] > nth_largest | i in 1..10]) <= n-1;

solve satisfy;

output ["第", show(n), "大值为: ", show(nth_largest)];

代码解释 #

• 变量n定义要查找的位次，示例中设置为3，对应数组的第3大值（示例数组排序后为[10,20,30,30,40,50,50,70,90,100]，第3大值为70）
• 辅助数组is_ge用于标记每个元素与目标值的大小关系
• 三个约束组合起来，精准锁定第n大值：保证至少n个元素大于等于目标值，同时最多n-1个元素大于目标值，确保目标值是第n大的元素

如果需要可复用的函数封装，可使用以下写法：

function var int: nth_largest(array[int] of int: arr, int: n) =
  let {
    var int: res;
    array[index_set(arr)] of var bool: is_ge;
  } in (
    forall(i in index_set(arr)) (is_ge[i] = (arr[i] >= res)) /\
    sum(is_ge) >= n /\
    sum([arr[i] > res | i in index_set(arr)]) <= n-1
  ) -> res;

% 使用示例
array[1..10] of 1..200 : t=[30,20,30,40,50,50,70,10,90,100];
var int : result = nth_largest(t, 3);

solve satisfy;

output ["第3大值为: ", show(result)];

内容的提问来源于stack exchange，提问作者jinzhu