四舍五入矩阵，保留行和列的总计 [英] Rounding a matrix, preserving row and column totals

问题描述

想要的:(伪)代码，用于以保留行和列总计的方式对矩阵进行四舍五入.

Wanted: (pseudo-)code for rounding a matrix in a manner that preserves row and column totals.

问题从非负整数的矢量X和Y开始，并带有Sum[X]==Sum[Y].想要在保留行和列总计的同时舍入X×Y/Sum[X].

Problem starts with vectors, X and Y, of non-negative integers, with Sum[X]==Sum[Y]. Want to round X×Y/Sum[X] while preserving row and column totals.

这是一种婚姻问题. Xa和Xb和Xc一样，需要进行一定数量的握手(呼叫该号码Xa)；以及Ya Yb Yc.无论出于何种原因，所有握手都在X和Y之间.当然Xa + Xb + Xc == Ya + Yb + Yc.握手应尽可能按比例分配.因此，要对四舍五入的X×Y/Sum[X]的行和列的总数保持不变.

This is a type of marriage problem. Xa needs to do some number of handshakes (call that number Xa), as do Xb and Xc; and also Ya Yb Yc. For whatever reason, all handshakes are between an X and a Y. Of course Xa + Xb + Xc == Ya + Yb + Yc. Handshaking is to be, as closely as possible, pro-rata. So want rounded X×Y/Sum[X] with unchanged row and column totals.

尽管 http://people.mpi-inf.mpg. de/〜doerr/papers/unbimatround.pdf 似乎是答案，它既没有算法也没有代码.

Though http://people.mpi-inf.mpg.de/~doerr/papers/unbimatround.pdf seems to be the answer, it has neither algorithm nor code.

请好心的读者，有公开的代码或伪代码吗?甚至是对算法的清晰解释?

Please kind readers, is there published code or pseudo-code? Or even a clear explanation of an algorithm?

推荐答案

您发布的论文说，矩阵的随机取整很可能满足您的约束条件.本文认为可以在O(nml)中进行计算，其中l是用于对矩阵进行随机处理的位数.因此，概率不取决于矩阵大小或使用的位.

The Paper you posted says that a randomized rounding of The matrix, satisfy your constraints with a high probability. In the paper is sayd that it can be computed in O(nml) where l is the number of bits that are used to randomized round the matrix. So the probability can not dependent on the matrix size or the used bits.

因此，请尝试以下算法:

So try the following algorithm:

1. For all x in your matrix do  
      r = random float number in [0,1]
      if r <= x - floor(x) then    
         x := ceil(x);  
      else  
         x := floor(x);  
2. check if the randomized rounded matrix fulfill the constrains.
   if so then end the algorithm
   else try again.

根据本文，这应该不需太多尝试.

According to the paper, this should not take too many trys.

这篇关于四舍五入矩阵，保留行和列的总计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！