Want caculate the n-th largest value in an array Use Minizinc

Viewed 54

Any boys can help me write a function to caculate the n-th largest value in an array ? for example :

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

In general to determine the nth largest numbers you first have to determine the n-1 larger numbers. If there is only 1 or 2, then you might be able to do something smarter, but in general I think the best supported solution is to use the arg_sort function to determine the order of all elements, and then choose the nth largest one.

This can be written as the following function:

function var int: nth_largest(array[$$E] of $$V: x, var int: n) =
  let {
    any: perm = arg_sort(x);
  } in x[perm[length(x)-n]];

In your fragment this can be used as:

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


function var int: nth_largest(array[$$E] of $$V: x, var int: n) =
  let {
    any: perm = arg_sort(x);
  } in x[perm[length(x)-n]];

Although you might want to find a more meaningful name for the variable, since shadowing names of variables and functions is generally frowned upon.

Reading @Dekker1's solution, here's what I had in mind. Instead of sort(x,y) the function y = sort(x) is used.

include "globals.mzn";
int: n = 10;
int: nth = 3;
array[1..n] of 1..200: t = [30,20,30,40,50,50,70,10,90,100];

var 1..200: nth_largest;

constraint
  nth_largest = sort(t)[n-nth+1]
;

Same idea using a function:

include "globals.mzn";
int: n = 10;
int: nth = 3;
array[1..n] of 1..200: t = [30,20,30,40,50,50,70,10,90,100];

var 1..200: nth_largest;

function var int: nth_largest_val(array[int] of var int: a, var int: m) =
    sort(a)[length(a)-m+1]
;

constraint
  nth_largest = nth_largest_val(t,nth)
;
 

Both give:

nth_largest = 70;

Update: Ignoring duplicates

Here is a variant which ignores duplicate values. nthis here a decision variable so we can see all solutions (and it makes it possible to "reverse" the constraint, see below).

include "globals.mzn";
int: n = 10;
var 1..n: nth; % : nth = 4;
array[1..n] of 1..200: t = [30,20,30,40,50,50,70,10,90,100];

var 1..200: nth_largest;

% Skipping duplicates
function var int: nth_largest_skip_dups(array[int] of var int: a, var int: nth) =
  let {
     var lb_array(a)..ub_array(a): v;
     constraint 
              % count the number of larger values in the unique set
              sum([ k > v | k in {a[j] | j in index_set(a) } ]) = nth -1
              % ensure that v is in a
              /\ exists(i in index_set(a)) (
                   v = a[i]
              );
  } in
    v
;

constraint
  nth_largest =  nth_largest_skip_dups(t,nth)
;
        
output ["nth:\(nth)\nlargest: \(nth_largest)\n" ];        

Here's the output:

nth:8
largest: 10
----------
nth:7
largest: 20
----------
nth:1
largest: 100
----------
nth:2
largest: 90
----------
nth:3
largest: 70
----------
nth:4
largest: 50
----------
nth:5
largest: 40
----------
nth:6
largest: 30
----------

Note about reversibility: If the following constraint is added the the constraint is reversed, i.e. we get what rank of the number 50:

constraint nth_largest = 50;

The output:

nth:4
largest: 50

A drawback is that it might be costly for large arrays, and it's better to use the first suggestion if you can ensure that the array has no duplicates.

Related