Pythonで行と列の合計を指定して有効な行列を見つけるプログラム

負でない値を持つ2つの配列rowSumとcolSumがあるとします。ここで、rowSum [i]はi番目の行の要素の合計であり、colSum[j]は2D行列のj番目の列の要素の合計です。指定されたrowSum値とcolSum値を満たす、サイズの非負の値（rowSumサイズx colSumサイズ）を持つ行列を見つける必要があります。

したがって、入力がrowSum =[13,14,12] colSum =[9,13,17]の場合、出力は

これを解決するには、次の手順に従います-

• matrix：=空行列を作成する
• 訪問：=新しいセット
• 関数minimum（）を定義します。これにはr、cが必要です
• min_total：=無限大
• type：=空白の文字列
• 範囲0からr-1のサイズのiの場合、do
  • r [i]
  • インデックス：=i
  • type：='row'
  • min_total：=r [i]

例

理解を深めるために、次の実装を見てみましょう-

def solve(r, c):
   matrix = [[0]*len(c) for _ in range(len(r))]
   visited = set()

   def minimum(r,c):
      min_total = float('inf')
   
      type = ''
      for i in range(len(r)):
         if(r[i] < min_total):
            index = i
            type = 'row'
            min_total = r[i]

      for i in range(len(c)):
         if(c[i] < min_total):
            min_total = c[i]
            type = 'col'
            index = i

      if(type == 'row'):
         r[index] = float('inf')

         for i in range(len(c)):
            if(c[i] != float('inf') and c[i] >= min_total):
               c[i] -= min_total
               matrix[index][i] = min_total
               break

      if(type == 'col'):
         c[index] = float('inf')
         for i in range(len(r)):
            if(r[i] != float('inf') and r[i] >= min_total):
               r[i] -= min_total
               matrix[i][index] = min_total
               break

      visited.add((index,type))

   while len(visited) != len(r)+len(c):
      minimum(r,c)

   return matrix

rowSum = [13,14,12]
colSum = [9,13,17]
print(solve(rowSum, colSum))

入力

[13,14,12], [9,13,17]

出力

[[9, 4, 0], [0, 9, 5], [0, 0, 12]]