Python में पंक्ति और स्तंभ योग दिए गए वैध मैट्रिक्स खोजने का प्रोग्राम

मान लीजिए हमारे पास दो ऐरे rowSum और colSum हैं जिनमें नॉन-नेगेटिव मान हैं जहां rowSum[i] में iवीं पंक्ति के तत्वों का योग है और colSum[j] में jवें स्तंभ के तत्वों का योग है एक 2D मैट्रिक्स का। हमें दिए गए rowSum और colSum मानों को संतुष्ट करने वाले नॉन-नेगेटिव मानों के आकार (len(rowSum) x len(colSum)) का कोई भी मैट्रिक्स ढूंढना है।

उदाहरण के लिए, यदि इनपुट है rowSum = [13,14,12], colSum = [9,13,17], तो आउटपुट होगा:

समाधान के चरण

1. matrix := खाली मैट्रिक्स बनाएं
2. visited := set()
3. minimum() फंक्शन परिभाषित करें जो r, c लेता है:
   • min_total := infinity
   • type := ""
   • i को 0 से len(r)-1 तक:
     • यदि r[i] < min_total:
       • index := i
       • type := 'row'
       • min_total := r[i]
   • i को 0 से len(c)-1 तक:
     • यदि c[i] < min_total:
       • min_total := c[i]
       • type := 'col'
       • index := i
   • यदि type == 'row':
     • r[index] := infinity
     • i को 0 से len(c)-1 तक:
       • यदि c[i] != infinity and c[i] >= min_total:
         • c[i] := c[i] - min_total
         • matrix[index][i] := min_total
         • लूप से बाहर निकलें
     • यदि type == 'col':
       • c[index] := infinity
       • i को 0 से len(r)-1 तक:
         • यदि r[i] != infinity and r[i] >= min_total:
           • r[i] := r[i] - min_total
           • matrix[i][index] := min_total
           • लूप से बाहर निकलें
     • visited.add((index, type))
     • मुख्य मेथड से:
       • while len(visited) != len(r) + len(c):
         • minimum(r, c)
       • matrix वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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