Карта верхней треугольной матрицы на вектор, пропускающий диагональ

Question

У меня есть проблема, которая может быть сведена к поиску способа отображения треугольной матрицы на вектор, пропускающий диагональ.

В основном нужно перевести этот код C++ с использованием библиотеки Gecode

// 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); 

В этот MiniZinc (функциональный) код

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

И мне нужно, чтобы выяснить, индекс в differences[?].

MiniZinc - это функционально-математический язык, не подходящий для петель. Итак, я должен сопоставить те индексы i и j, которые касаются всех, и только ячейки верхней треугольной матрицы, пропуская ее диагональ, до k, которая выставляет эти ячейки от 0 до любого.

Если бы это была правильной треугольной матрицы (это не так), решение like this бы

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, are с нулевой точкой. Ваш код MiniZinc использует индексы i, j, которые начинаются с 1 (1 < = i < = 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 < = я < М, 0 < = у < N [Если вы снова нужны ваши индексы, чтобы начать с 1 , замените i i-1 и j j-1 в приведенной выше формуле]. Это касается всех ячеек верхней треугольной матрицы, а также «дополнительного блока на стороне» квадрата, который возникает при N> M. То есть он касается всех ячеек (i, j), таких, что i < j для 0 < = я < М, 0 < < = у Н.

---

Полный код:

% 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, где nece ssary):

% 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"];