与えられた行と列の和から2次元配列を生成する

Question

配列の各行と列の合計が分かっている整数の配列を生成したいと思います。たとえば、4行4列の配列アレイは次のようになり

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 

次いでIにより、各行及び各列を合計する場合：

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] ; 
    } 
} 

次にC++と、それは1と100の間の数字でランダム擬似移入

rowSumが、私はこの時点で何をしようとしている{191,228,141,228}とcolumnSum = {156,176,248,208}

だろう私は別の何千ものがあります理解しrowSumとcolumnSumを満足させる任意のランダムな4x4の1〜100の配列を生成することです同じ行と列の合計まで集計する配列と、それを生成するコードの部分を書くことを試みてきましたが、誰かが私に手がかりを与えることができれば本当に感謝しています。

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; 
      } 
     } 
    } 
} 

この配列はもちろんのランダムではありません。

言ったよりも簡単に行われます。

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

結果の値が所望の範囲の外にこぼれないということに注意して：一つは、ランダムにX1、X2、Y1、Y2およびDを選択して実行することで、それをランダム化することができます。

Answer 2

コメントに記載されている素早く汚れたブルートフォース検索があります。それはあなたに出発点を与えるべきです。これはCではなくCです。

あなたはそれを言ったことはありませんが、行列要素が非負であることを前提としています。したがって、次の配列要素の値を代入すると、各要素a [i] [j]が[0..min（rowsum [i]、colsum [j]）]に値を持ち、可能な将来の解決策は認められません。例えば

#include <stdio.h> 

int a[4][4] = { 
    {-1, -1, -1, -1}, 
    {-1, -1, -1, -1}, 
    {-1, -1, -1, -1}, 
    {-1, -1, -1, -1}}; 
int rs[] = {191, 228, 141, 228}; 
int cs[] = {156, 176, 248, 208}; 
long long n_solutions = 0; 

void research(int i, int j, int ii, int jj, int val); 
void print_a(void); 

void search(int i, int j) { 
    if (j < 3) { 
    if (i < 3) { 
     int m = rs[i] < cs[j] ? rs[i] : cs[j]; 
     for (int val = 0; val <= m; ++val) research(i, j, i, j + 1, val); 
    } else { 
     if (rs[3] >= cs[j]) research(i, j, i, j + 1, cs[j]); 
    } 
    } else { 
    if (i < 3) { 
     if (cs[j] >= rs[i]) research(i, 3, i + 1, 0, rs[i]); 
    } else { 
     if (rs[3] == cs[3]) { 
     a[3][3] = rs[i]; 
     if (++n_solutions % 100000000 == 0) { 
      printf("\n%lld\n", n_solutions); 
      print_a(); 
     } 
     a[3][3] = -1; 
     } 
    } 
    } 
} 

void research(int i, int j, int ii, int jj, int val) { 
    a[i][j] = val; rs[i] -= val; cs[j] -= val; 
    search(ii, jj); 
    rs[i] += val; cs[j] += val; a[i][j] = -1; 
} 

void print_a(void) { 
    for (int i = 0; i < 4; ++i) { 
    for (int j = 0; j < 4; ++j) 
     printf("%4d", a[i][j]); 
    printf("\n"); 
    } 
} 

int main(void) { 
    search(0, 0); 
    printf("Total solutions: %lld\n", n_solutions); 
    return 0; 
} 

あなたはこれでシンプルなforループを交換する場合、あなたは左上隅に非常に多くのゼロを得ることはありません。

int b = m/2; // m/2 can be replaced with any int in [0..m], e.g. a random value. 
research(i, j, i, j + 1, b); 
for (int d = 1; b + d <= m || b - d >= 0; ++d) { 
    if (b + d <= m) research(i, j, i, j + 1, b + d); 
    if (b - d >= 0) research(i, j, i, j + 1, b - d); 
} 

ここで2億ソリューションです：