पायथन में पहले n प्राकृतिक संख्याओं के क्रमचय से मैजिक सेट की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास पहले n प्राकृतिक संख्याओं वाली एक सरणी A है, और सरणी A का एक क्रमचय P{p1, p2, ... pn} है। हमें जांचना है कि कितने मैजिक सेट हैं। एक क्रमचय को मैजिक सेट कहा जाता है, यदि यह इन कुछ नियमों को पूरा करता है:

• यदि हमारे पास k है, तो स्थितियों a[1], a[2], ... a[k] में तत्व अपने आसन्न तत्वों से कम हैं [P[a[i] - 1] > P[a[i]] < P[a[i] + 1]]
• यदि हमारे पास l है, तो स्थितियों b[1], b[2], ... b[l] में तत्व अपने आसन्न तत्वों से अधिक हैं [P[b[i] - 1] < P[b[i]] > P[b[i] + 1]]

तो, यदि इनपुट n = 4, k = 1, l = 1, k_vals = [2], l_vals = [3] है, तो आउटपुट 5 होगा क्योंकि: N = 4, a[1] = 2 और b[1] = 3। तो पांच क्रमचय हैं [2,1,4,3], [3,2,4,1], [4,2,3,1], [3,1,4,2], [4,1,3,2]।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• p := 10^9+7
• F := आकार n+2 की एक सरणी जिसे 0 से भरा गया है
• k_vals में प्रत्येक a के लिए, करें
  • यदि F[a - 1], 1 है या F[a + 1], 1 है, तो
    • यदि F[a - 1], 1 है या F[a + 1], 1 है, तो
      • p := null
    • F[a] := 1
• l_vals में प्रत्येक b के लिए, करें
  • यदि F[b], 1 है या F[b - 1], -1 है या F[b + 1], -1 है, तो
    • p := null
  • F[b] := -1
• यदि p, null के समान है, तो
  • 0 लौटाएं
• अन्यथा,
  • A := आकार n+1 की एक सरणी जिसे 0 से भरा गया है
  • B := आकार n+1 की एक सरणी जिसे 0 से भरा गया है
  • FF := आकार n+1 की एक सरणी जिसे null से भरा गया है
  • i को 1 से n तक की रेंज में, करें
    • FF[i] := F[i] - F[i - 1]
  • A[1] := 1
  • i को 2 से n तक की रेंज में, करें
    • j को 1 से i तक की रेंज में, करें
      • यदि FF[i] > 0, तो
        • B[j] :=(B[j - 1] + A[j - 1]) mod p
      • अन्यथा जब FF[i] < 0, तो
        • B[j] :=(B[j - 1] + A[i - 1] - A[j - 1]) mod p
      • अन्यथा,
        • B[j] :=(B[j - 1] + A[i - 1]) mod p
    • A और B को स्वैप करें
  • A[n] लौटाएं

उदाहरण

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

def solve(n, k, l, k_vals, l_vals): p = 10**9+7 F = [0] * (n + 2) for a in k_vals: if F[a - 1] == 1 or F[a + 1] == 1: p = None F[a] = 1 for b in l_vals: if F[b] == 1 or F[b - 1] == -1 or F[b + 1] == -1: p = None F[b] = -1 if p == None: return 0 else: A = [0] * (n + 1) B = [0] * (n + 1) FF = [None] * (n + 1) for i in range(1, n + 1): FF[i] = F[i] - F[i - 1] A[1] = 1 for i in range(2, n + 1): for j in range(1, i + 1): if FF[i] > 0: B[j] = (B[j - 1] + A[j - 1]) % p elif FF[i] < 0: B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) % p else: B[j] = (B[j - 1] + A[i - 1]) % p A, B = B, A return A[n] n = 4 k = 1 l = 1 k_vals = [2] l_vals = [3] print(solve(n, k, l, k_vals, l_vals))

इनपुट

4, 1, 1, [2], [3] 

आउटपुट

5