पायथन में सही क्रमपरिवर्तन कहां हो सकता है, यह जानने के लिए प्रोग्राम

मान लीजिए, हमें एक संख्या n दी गई है और हमें n तक के धनात्मक पूर्णांकों के साथ सभी संभावित क्रमपरिवर्तन लिखने के लिए कहा गया है। क्रमपरिवर्तन तब लेक्सिकोग्राफिक रूप से क्रमबद्ध होते हैं और 1 से n तक गिने जाते हैं। सभी क्रमपरिवर्तनों के बीच, एक क्रमपरिवर्तन लिया जाता है और इसे विशेष क्रमपरिवर्तन कहा जाता है। अब, विशेष क्रमपरिवर्तन के बीच; मूल्यों को भुलाया जा सकता है। भूले हुए मानों को फिर 0s से बदल दिया जाता है। हमें उन क्रमपरिवर्तनों को खोजना होगा जो मूल क्रमपरिवर्तन के बराबर हो सकते हैं और फिर हम योग प्राप्त करने के लिए उनकी परिप्रेक्ष्य संख्या जोड़ते हैं। योग मान प्रोग्राम के आउटपुट के रूप में लौटाया जाता है।

इसलिए, यदि इनपुट विशेष क्रमपरिवर्तन (input_arr) =[0, 2, 0], n =3 की तरह है, तो आउटपुट 7 होगा। दो संभावित क्रमपरिवर्तन हो सकते हैं। एक [1, 2, 3] और दूसरा [3, 2, 1] है। इन क्रमपरिवर्तनों की संख्या क्रमशः 2 और 5 है। तो, परिणाम 5 + 2 =7. होगा।

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

मॉड:=10^9 + 7
i2:=2 ^ (मॉड्यूलो - 2) मोडुलो
तथ्य:=1 मान वाली एक नई सूची
x श्रेणी 1 से n+1 के लिए, करें
- तथ्य के अंत में (तथ्य का अंतिम आइटम * x) मोड मॉड्यूल डालें
cnt :=input_arr में 0 की घटनाओं की संख्या
यदि सीएनटी शून्य के समान है, तो
- res :=0
- देखा_सूची :=एक नई सूची
- प्रत्येक इंडेक्स के लिए मैं 1 से शुरू करता हूं और आइटम x input_arr में, करता हूं
  - tmp_val :=वह सूचकांक जहां x को क्रमबद्ध क्रम को बनाए रखते हुए देखा सूची में डाला जा सकता है
  - res :=res + fact[n-i] *(x - 1 - tmp_val)
  - res :=res modulo
  - x को देखा_सूची में tmp_val स्थिति में डालें
- रिटर्न रेस + 1
अन्यथा,
- ik :=(cnt ^ (modulo-2)) mod modulo
- मिस :=आकार n की एक नई सूची को सही मान के साथ प्रारंभ किया गया
- इनपुट_एआर में प्रत्येक एक्स के लिए, करें
  - यदि x, 0 के समान नहीं है, तो
    - मिस [x - 1] :=गलत
- miss_srtd :=एक नई सूची
- tmp :=0
- प्रत्येक इंडेक्स के लिए मैं 1 से शुरू कर रहा हूं, और आइटम एक्स मिस में है, करो
  - यदि x शून्य नहीं है, तो
    - miss_srtd के अंत में i डालें
    - tmp :=tmp + i
- पूर्व :=0 से आरंभ की गई एक नई सूची
- मिस में प्रत्येक x के लिए, करें
  - प्री के अंत में प्री[-1] + x डालें
- cnt_cu :=0
- s :=tmp mod modulo * ik mod modulo
- srtdw :=एक नई सूची
- res :=0
- z :=0
- प्रत्येक इंडेक्स के लिए मैं 1 से शुरू करता हूं और आइटम x input_arr में, करता हूं
  - यदि x शून्य नहीं है, तो
    - l :=वह स्थिति जहां x को क्रमबद्ध क्रम को बनाए रखते हुए srtdw में डाला जा सकता है
    - tmp_val :=वह स्थिति जहां x को क्रमबद्ध क्रम में रखते हुए srtdw में डाला जा सकता है
    - l :=l + z * (वह स्थिति जहां x को क्रमबद्ध क्रम को बनाए रखते हुए Miss_srtd में डाला जा सकता है) mod modulo * ik mod modulo
    - p :=x - 1 - l
    - p :=p * fact[cnt]
    - p :=p modulo
    - srtdw में tmp_val स्थिति में x डालें
    - cnt_cu :=cnt_cu + cnt - पूर्व[x]
  - अन्यथा,
    - l :=cnt_cu
    - l :=l * ik
    - l :=l + z * i2 modulo
    - p :=s - 1 - l
    - p :=p * fact[cnt]
    - p :=p modulo
    - z :=z + 1
    - res :=res + p * fact[n-i] mod modulo
    - res :=res modulo
- वापसी(res + fact[cnt]) मोडुलो

उदाहरण

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

import bisect

def solve(input_arr, n):

   modulo = 10 ** 9 + 7
   i2 = pow(2, modulo-2, modulo)
   fact = [1]
   for x in range(1, n+1):
      fact.append(fact[-1] * x % modulo)

   cnt = input_arr.count(0)

   if not cnt:
      res = 0
      seen_list = []
      for i, x in enumerate(input_arr, 1):
         tmp_val = bisect.bisect(seen_list, x)
         res += fact[n-i] * (x - 1 - tmp_val)
         res %= modulo
         seen_list.insert(tmp_val, x)
      return res + 1
   else:
      ik = pow(cnt, modulo-2, modulo)
      miss = [True] * n
      for x in input_arr:
         if x != 0: miss[x-1] = False
      miss_srtd = []
      tmp = 0
      for i, x in enumerate(miss, 1):
         if x:
            miss_srtd.append(i)
            tmp += i
      pre = [0]
      for x in miss:
         pre.append(pre[-1] + x)
      cnt_cu = 0
      s = tmp % modulo * ik % modulo
      srtdw = []
      res = z = 0
      for i, x in enumerate(input_arr, 1):
         if x:
            l = tmp_val = bisect.bisect(srtdw, x)
            l += z * bisect.bisect(miss_srtd, x) % modulo * ik % modulo
            p = x - 1 - l
            p *= fact[cnt]
            p %= modulo
            srtdw.insert(tmp_val, x)
            cnt_cu += cnt - pre[x]
         else:
            l = cnt_cu
            l *= ik
            l += z * i2 % modulo
            p = s - 1 - l
            p *= fact[cnt]
            p %= modulo
            z += 1
         res += p * fact[n-i] % modulo
         res %= modulo
      return (res + fact[cnt])%modulo

print(solve([0, 2, 0], 3))

इनपुट

[0, 2, 0], 3