Minizinc array sorting

Question

Lets say I have an array declaration looking like this

array[1..5] of int: temp = [1,0,5,0,3];

Is there a way to initiate a new array looking the same as temp but without the 0's? The result would look like the following

[1,5,3]

or sort the array in such a way that the 0's would be either in the beginning or in the end of the array, which would be

[0,0,1,5,3]

or

[1,5,3,0,0]

Thanks

Answer 1

Another alternative:

A 1:1 mapping between the two arrays is established as an array of unique index values (= array positions). These indices are then sorted. The comparison weights elements higher if they point to a zero. Thus, the zero values are shifted to the back while leaving the order of the non-zero elements unchanged.

int: n = 5;
int: INF = 99999;    %  infinity
array[1..n] of var 0..5: s;
array[1..n] of var 1..n: map;
array[1..n] of var 0..5: s2;

solve satisfy;

%  set s[]
constraint
   s = [1,0,5,0,3]
;
%  1:1 mapping between s[] and s2[]
constraint 
  forall (i in 1..n) (
    exists(j in 1..n) (
      map[j] = i
    )
  )
;
constraint
   forall(i in 1..n) (
      s2[i] = s[map[i]]
   )
;
%  sort the map and move zero values to the back
constraint
   forall(i in 1..n-1) (
     (if s2[i] != 0 then map[i] else INF endif) <= 
     (if s2[i+1] != 0 then map[i+1] else INF endif)
   )
;

output 
[ 
  "s: \(s)\n",
  "map: \(map)\n",
  "s2: \(s2)\n",
]
;    

Output:

s: [1, 0, 5, 0, 3]
map: [1, 3, 5, 4, 2]
s2: [1, 5, 3, 0, 0]

Answer 2

Even though Axel has answered this, I'll show another approach which - in my book is a little neater.

• Case 1: the array ("temp") is a constant array. Then one can simply write

  array[int] of int: temp2 = [temp[i] | i in index_set(temp) where temp[i] != 0];

MiniZinc 2 (in contrast to version 1.*) don't need the size declaration if it can be calculated; it suffices to just use "array[int]". Also, "index_set" is used to be a little more general, e.g. to handle cases where the indices are from 0..4 (see the commented line).

• Case 2: the array ("s") is an array of decision variables

If the array to handle is decision variables, we don't know (per definition) how many 0's there are and must rely on the alternative variant, namely to sort the array. One can then use the "sort" function, as shown in the model.

 include "globals.mzn";

 % constant
 array[1..5] of int: temp = [1,0,5,0,3];
 % array[0..4] of int: temp = array1d(0..4, [1,0,5,0,3]);
 array[int] of int: temp2 = [temp[i] | i in index_set(temp) where temp[i] != 0];

 % decision variables
 array[1..5] of var int: s;
 array[1..5] of var int: s2 = sort(s); % NOT CORRECT, see model below

 solve satisfy;

 constraint
    s = [1,0,5,0,3]
 ;

 %  show our variables
 output 
 [
    "temp: \(temp)\n",
    "temp2: \(temp2)\n",

    "s: \(s)\n",
    "s2: \(s2)\n",
 ];

Update

For the stable version of decision variables, this works what I can see. It calculating the position where to place this number depending on if "s[i]" is 0 or not. Not very pretty though.

 int: n = 5;
 array[1..n] of var 0..5: s;
 array[1..n] of var lb_array(s)..ub_array(s): s2;

 solve satisfy;

 constraint
   s = [1,0,5,0,3] /\
   forall(i in 1..n) (
      if s[i] != 0 then
        s2[sum([s[j]!=0 | j in 1..i-1])+1] = s[i]
      else 
        s2[sum([s[j]!=0 | j in 1..n]) + sum([s[j]=0 | j in 1..i-1])+1 ] = 0
      endif
   )
;

output 
[ 
  "s: \(s)\n",
  "s2: \(s2)\n",
]
;

The output is

s: [1, 0, 5, 0, 3]
s2: [1, 5, 3, 0, 0]

Answer 3

Using MiniZinc 2, this can be done as follows:

array[1..5] of int: temp = [1,0,5,0,3];
%  calculate upper bound of temp index
int: i_max = max(index_set(temp));
%  use array comprehension to count non-zero elements
int: temp_non_zero = sum([1 | i in 1..i_max where temp[i] != 0]);
%  copy non-zero elements to new array
array[1..temp_non_zero] of int: temp2 = [temp[i] | i in 1..i_max where temp[i] != 0];
%  calculate upper bound for temp2 index
int: i2_max = max(index_set(temp2));

solve satisfy;

%  show our variables
output 
["\ni_max=" ++ show(i_max)] 
++ ["\ni2_max=" ++ show(i2_max)] 
++ ["\n" ++ show(temp2[i]) | i in 1..i2_max] 
;