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