Map of the upper triangular matrix on a vector skipping the diagonal

Question

I have a problem that can be reduced to finding a way to match a triangular matrix to a vector that skips the diagonal.

Basically I need to translate this code to C ++ using Gecode libraries

// implied constraints
for (int k=0, i=0; i<n-1; i++)
  for (int j=i+1; j<n; j++, k++)
    rel(*this, d[k], IRT_GQ, (j-i)*(j-i+1)/2);

In this MiniZinc (functional) code

constraint
   forall ( i in 1..m-1 , j in i+1..m )
      ( (differences[?]) >=  (floor(int2float(( j-i )*( j-i+1 )) / int2float(2)) ));

And I need to find out the index at differences[?].

MiniZinc is a functional mathematical language that is not suitable for loops. Therefore, I have to compare those indices i and j that concern everyone, and only the cells of the upper triangular matrix, skipping its diagonal, to k, which numbers these cells from 0 to any.

If it were a regular triangular matrix (this is not so), then a solution like this would fulfill

index = x + (y+1)*y/2

, , n*n , 0 n-1, n*m.

Minizinc

% modified version of the file found at https://github.com/MiniZinc/minizinc-benchmarks/blob/master/golomb/golomb.mzn

include "alldifferent.mzn";

int: m;
int: n = m*m;
array[1..m] of var 0..n: mark;
array[int] of var 0..n: differences = [mark[j] - mark[i] | i in 1..m, j in i+1..m];

constraint mark[1] = 0;

constraint forall ( i in 1..m-1 ) ( mark[i] < mark[i+1] );

% this version of the constraint works
constraint forall ( i in 1..m-1 , j in i+1..m )
    ( (mark[j] - mark[i]) >= (floor(int2float(( j-i )*( j-i+1 )) / int2float(2))) );

%this version does not
%constraint forall ( i in 1..m-1, j in i+1..m )
%    ( (differences[(i-1) + ((j-2)*(j-1)) div 2]) >= (floor(int2float(( j-i )*( j-i+1 )) / int2float(2))) );

constraint alldifferent(differences);

constraint differences[1] < differences[(m*(m-1)) div 2];

solve :: int_search(mark, input_order, indomain, complete) minimize mark[m];

output ["golomb ", show(mark), "\n"];

.

Answer 1

. , , index = x + (y+1)*y/2, , , , , . , , index = x + ((y-1)y)/2 (. https://math.stackexchange.com/questions/646117/how-to-find-a-function-mapping-matrix-indices).

, , , , : x, y, . MiniZinc i, j, 1 (1 <= <= m), 1 <= j <= m)). , 1, T(i,j) = i + ((j-2)(j-1))/2. :

constraint
   forall ( i in 1..m-1 , j in i+1..m )
      ((distances[(i + ((j-2)*(j-1)) div 2]) >= ...

, (j-2)(j-1) 2, 2 ( / ).

---

, m*m.
M*N, :

0 <= < M, 0 <= j < N [ , 1, i-1 j j-1 ]. , " " , N > M. (i, j), , < j 0 <= < M, 0 <= j < N.

---

:

% original: https://github.com/MiniZinc/minizinc-benchmarks/blob/master/golomb/golomb.mzn

include "alldifferent.mzn";

int: m;
int: n = m*m;
array[1..m] of var 0..n: mark;
array[1..(m*(m-1)) div 2] of var 0..n: differences;

constraint mark[1] = 0;
constraint forall ( i in 1..m-1 ) ( mark[i] < mark[i+1] );
constraint alldifferent(differences);
constraint forall (i,j in 1..m where j > i)
    (differences[i + ((j-1)*(j-2)) div 2] = mark[j] - mark[i]);
constraint forall (i,j in 1..m where j > i)
    (differences[i + ((j-1)*(j-2)) div 2] >= (floor(int2float(( j-i )*( j-i+1 )) / int2float(2))));
constraint differences[1] < differences[(m*(m-1)) div 2];

solve :: int_search(mark, input_order, indomain, complete)
    minimize mark[m];

output ["golomb ", show(mark), "\n"];

( j, ):

% original: https://github.com/MiniZinc/minizinc-benchmarks/blob/master/golomb/golomb.mzn

include "alldifferent.mzn";

int: m;
int: n = m*m;
array[1..m] of var 0..n: mark;
array[1..(m*(m-1)) div 2] of var 0..n: differences;

constraint mark[1] = 0;
constraint forall ( i in 1..m-1 ) ( mark[i] < mark[i+1] );
constraint alldifferent(differences);
constraint forall (i,j in 1..m where i > j)
    (differences[j + ((i-1)*(i-2)) div 2] = mark[i] - mark[j]);
constraint forall (i,j in 1..m where i > j)
    (differences[j + ((i-1)*(i-2)) div 2] >= (floor(int2float(( i-j )*( i-j+1 )) / int2float(2))));
constraint differences[1] < differences[(m*(m-1)) div 2];

solve :: int_search(mark, input_order, indomain, complete)
    minimize mark[m];

output ["golomb ", show(mark), "\n"];