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

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

यदि हमारे पास k है, तो स्थिति a[1], a[2], ... a[k] में अवयव उनके आसन्न तत्वों से कम हैं [P[a[i] - 1]> P[a [i]] <पी[ए[i] + 1]]
यदि हमारे पास एल है, तो स्थिति बी [1], बी [2], ... बी [एल] में तत्व उनके आसन्न तत्वों से अधिक हैं [पी [बी [i] - 1] <पी [बी [ i]]> पी[बी[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 :=शून्य
  - F[a] :=1
l_vals में प्रत्येक b के लिए, करें
- यदि F[b] 1 है या F[b - 1] -1 है या F[b + 1] -1 है, तो
  - p :=शून्य
- एफ[बी] :=-1
यदि p शून्य के समान है, तो
- वापसी 0
अन्यथा,
- A :=आकार n+1 की एक सरणी और 0 से भरें
- B :=n+1 आकार की एक सरणी और 0 से भरें
- FF:=आकार n+1 की एक सरणी और शून्य से भरें
- 1 से n की श्रेणी में i के लिए, करें
  - FF[i] :=F[i] - F[i - 1]
- ए[1] :=1
- 2 से n की श्रेणी में i के लिए, करें
  - जे के लिए 1 से i की श्रेणी में, करें
    - अगर एफएफ[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[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]