c++ - 从其行和列的给定总和生成一个二维整数数组

Question

我想生成一个整数数组，其中数组中每行和每列的总和是已知的，例如，如果我在 C++ 中创建一个 4 x 4 数组，然后用 1 到 100 之间的数字伪随机填充它:

int array[4][4] = {} ;
for(int x = 0 ; x<4 ; x++){
   for(int y = 0 ; y<4 ; y++){
      array[x][y] = rand() % 100 + 1 ;
   }
}

数组将是:

 8, 50, 74, 59
31, 73, 45, 79
24, 10, 41, 66
93, 43, 88,  4

然后如果我对每一行和每一列求和:

int rowSum[4] = {} ; 
int columnSum[4] = {} ; 
for(int x = 0 ; x < 4; x++){
    for(int y = 0 ; y < 4; y++){
        rowSum[x] += array[x][y] ;
        columnSum[y] += array[x][y] ;
    }
}

rowSum 为 {191,228,141,228} columnSum = {156,176,248,208}

此时我要做的是生成任何随机的 4x4 1~100 数组，以满足 rowSum 和 columnSum 我知道有成千上万种不同的总和为相同行和列总和的数组，我一直在尝试编写将生成它的代码部分，如果有人能给我线索，我将不胜感激。

Answer 1

很容易找到一些解决方案。

从生成总和为给定值的行开始。它可以简单到使每一行中的所有值都近似等于 rowSum[i]/n，给或取一个。当然，此时列的总和将不匹配。

现在从最左边到最右边固定列。要修复第 i 列，请在列条目之间平均分配所需总和与实际总和之间的差值，然后通过在项目 i+1.. 之间平均分配增加值来修复每一行。 .n 行。

做起来比说起来容易:

void reconstruct (int array[4][4], int rows[4], int cols[4])
{   
    // build an array with each row adding up to the correct row sum
    for (int x = 0; x < 4; x++){
        int s = rows[x]; 
        for(int y = 0; y < 4 ; y++){
            array[x][y] = s / (4 - y);
            s -= array[x][y];
        }
    }

    // adjust columns
    for(int y = 0; y < 4 ; y++){
        // calculate the adjustment
        int s = 0; 
        for (int x = 0; x < 4; x++){
            s += array[x][y];
        }
        int diff = s - cols[y];
        // adjust the column by diff
        for (int x = 0; x < 4; x++){
            int k = diff / (4 - x);
            array[x][y] -= k; 
            diff -= k;
            // adjust the row by k
            for (int yy = y + 1; yy < 4; ++yy)
            {   
                int corr = k / (4 - yy);
                array[x][yy] += corr;
                k -= corr;
            }
        }
    }
}

这个数组当然不是随机的。可以通过随机选择 x1、x2、y1、y2 和 d 来随机化它并执行:

 array[x1][y1] += d
 array[x1][y2] -= d
 array[x2][y1] -= d
 array[x2][y2] += d

注意结果值不会超出所需范围。