पायथन में उन संख्याओं का योग ढूंढना जहां सही परम्यूटेशन हो सकता है

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

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

समाधान दृष्टिकोण

यह समस्या कॉम्बिनेटोरिक्स और मॉड्यूलर अंकगणित का उपयोग करती है। मुख्य विचार फैक्टोरियल और बाइनरी सर्च (bisect) का उपयोग करके वैध परम्यूटेशन की रैंक की गणना करना है।

मॉड्यूलो 10^9 + 7 और फैक्टोरियल सरणी की पूर्व-गणना करें।
यदि कोई शून्य नहीं है, तो बाइनरी सर्च का उपयोग करके परम्यूटेशन की रैंक सीधे गणना करें।
यदि शून्य हैं (भूले हुए मान), तो लापता संख्याओं को संभालने के लिए कॉम्बिनेटोरिक फॉर्मूला और मॉड्यूलर व्युत्क्रम का उपयोग करें।
दोनों दिशाओं (फॉरवर्ड और बैकवर्ड) को संभालने के लिए प्रीफिक्स सम और सॉर्ट की गई लापता मानों की सूची का उपयोग करें।

पायथन कार्यान्वयन

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 = 0
        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