在跳过对角线的向量上映射上三角矩阵 [英] Map upper triangular matrix on vector skipping the diagonal

问题描述

我有一个问题可以归结为寻找一种将三角形矩阵映射到跳过对角线的矢量的方法.

I have a problem that could be boiled down to finding a way of mapping a triangular matrix to a vector skipping the diagonal.

基本上，我需要使用Gecode库翻译此C ++代码

Basically I need to translate this C++ code using the 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);

进入此MiniZinc(功能性)代码

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

我需要弄清楚differences[?]中的索引.

And I need to figure out the index in differences[?].

MiniZinc是一种功能/数学语言，没有适当的for循环. 因此，我必须将触及所有且仅触及上三角矩阵对角线的所有单元格的索引i和j映射到一个k，以将这些单元格从0编号为任意数字.

MiniZinc is a functional/mathematical language with no proper for loops. So I have to map those indexes i and j that are touching all and only the cells of an upper triangular matrix, skipping its diagonal, to a k that numbers those cells from 0 to whatever.

如果这是一个规则的三角矩阵(不是)，那么这样的解决方案就可以

If this was a regular triangular matrix (it's not), a solution like this would do

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

我正在处理的矩阵是一个正方形的n*n矩阵，索引从0到n-1，但是为n*m矩阵提供一个更通用的解决方案将是个不错的选择.

The matrix I'm handling is a square n*n matrix with indexes going from 0 to n-1, but it would be nice to provide a more general solution for an n*m matrix.

这是完整的Minizinc代码

Here's the full Minizinc code

% 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/如何查找功能映射矩阵索引).

Be careful. The formula you found from that link, index = x + (y+1)*y/2, includes the diagonal entries, and is for a lower triangular matrix, which I gather is not what you want. The exact formula you are looking for is actually index = x + ((y-1)y)/2 (see: https://math.stackexchange.com/questions/646117/how-to-find-a-function-mapping-matrix-indices).

同样，当心，我给您的这个公式假设您的索引:x，y是基于从零开始的.您的MiniZinc代码使用的索引i，j是从1 开始(1 <= i< = m)，1 <= j< = m)).对于从1开始的索引，公式为T(i,j) = i + ((j-2)(j-1))/2.因此您的代码应如下所示:

Again, watch out, this formula I gave you assumes your indices: x,y, are zero-based. Your MiniZinc code is using indices i,j that start from 1 (1 <= i <= m), 1 <= j <= m)). For indices that start from 1, the formula is T(i,j) = i + ((j-2)(j-1))/2. So your code should look like:

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一起使用(不必担心转换为浮点数或从浮点数转换为浮点数).

Note that (j-2)(j-1) will always be a multiple of 2, so we can just use integer division with divisor 2 (no need to worry about converting to/from floats).

以上假设您使用的是正方形m*m矩阵.
为了概括为M*N矩形矩阵，一个公式可以是:

The above assumes you are using a square m*m matrix.
To generalise to a M*N rectangular matrix, one formula could be:

其中0< = i< M，0 ＜＝ j ＜1. N [如果再次出现，则需要从1开始的索引，在上式中将i替换为i-1，将j替换为j-1].这触摸了上三角矩阵的所有单元以及在N> M时发生的正方形的边上的额外块".也就是说，它触摸了所有单元(i，j)，使得i≤i. j表示0< = i< M，0≤j≤否

where 0 <= i < M, 0<= j < N [If you again, need your indices to start from 1, replace i with i-1 and j with j-1 in the above formula]. This touches all of cells of an upper triangular matrix as well as the 'extra block on the side' of the square that occurs when N > M. That is, it touches all cells (i,j) such that i < j for 0 <= i < 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"];

较低的三角形版本(采用先前的代码并在必要时交换i和j):

Lower triangular version (take previous code and swap i and j where necessary):

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

这篇关于在跳过对角线的向量上映射上三角矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！