Find the smallest alldifferent array whose sum is n

user_121259 0
Viewed 86

This seems like such a simple problem, but I can't find a simple way to represent this in MiniZinc.

include "globals.mzn";

int: target;
int: max_length;

var 1..max_length: length;

array[1..length] of int: t;

constraint sum(t) = target;
constraint alldifferent(t);

solve minimize length;

This program errors with: MiniZinc: type error: type-inst must be par set but is ``var set of int'

Is there a clean/simple way to represent this problem in MiniZinc?

minizinc
1 Answers

Arrays in MiniZinc have a fixed size. The compiler is therefore saying that array[1..length] of int: t is not allowed, because length is a variable.

The alternative that MiniZinc offers is arrays with optional types, these are values that might exist. This means that when you write something like [t | t in 1..length], it will actually give you an array of 1..maxlength, but some elements can be marked as absent/<>.

For this particular problem you are also overlooking the fact that t should itself be a array of variables. The values of t are not yet known when at compile-time. A better way to formulate this problem would thus be to allow the values of t to be 0 when they are beyond the chosen length:

include "globals.mzn";

int: target;
int: max_length;

var 1..max_length: length;

array[1..max_length] of var int: t;

constraint sum(t) = target;
constraint alldifferent_except_0(t);
constraint forall(i in length+1..max_length) (t[i] = 0);

solve minimize length;

The next step to improve the model would be to ensure that the initial domain of t makes sense and instead of being all different, forcing an ordering would be equivalent, but eliminate some symmetry in the possible solutions.

user_13515970
Related