四舍五入矩阵，保留行和列的总计

本文介绍了四舍五入矩阵，保留行和列的总计的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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.

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

Though 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.