डुप्लिकेट युक्त एक अनुक्रम के अद्वितीय क्रमपरिवर्तन मैपिंग के लिए संख्या

Question

मैं एक एल्गोरिदम खोज रहा हूं जो अनुक्रम के अद्वितीय क्रमपरिवर्तन के लिए एक संख्या को मैप कर सकता है। मुझे लेमर कोड और फैक्टरियल नंबर सिस्टम के बारे में पता चला है, एक समान प्रश्न, Fast permutation -> number -> permutation mapping algorithms, लेकिन यह प्रश्न उस मामले से निपटता नहीं है जहां अनुक्रम में डुप्लिकेट तत्व हैं।

उदाहरण के लिए, अनुक्रम 'एएएबीबीसी' लें। 6 हैं! = 720 तरीके जिन्हें व्यवस्थित किया जा सकता है, लेकिन मेरा मानना ​​है कि केवल 6 हैं!/(3! * 2! * 1!) = 60 इस अनुक्रम का अद्वितीय क्रमपरिवर्तन। मैं इन मामलों में क्रमपरिवर्तन के लिए किसी नंबर को कैसे मैप कर सकता हूं?

संपादित करें: 'सेट' शब्द 'अनुक्रम' में बदल दिया गया है।

Answer 1

क्रमपरिवर्तन से संख्या को

:

:

Let कश्मीर चरित्र वर्गों (AAABBC तीन चरित्र वर्गों है उदाहरण) की संख्या हो

एन [के] प्रत्येक चरित्र वर्ग में तत्वों की संख्या होने दें। (उदाहरण: एएएबीबीसी के लिए, हमारे पास एन [के] = [3,2,1] है, और एन = योग (एन [के])

अनुक्रम का प्रत्येक कानूनी क्रमपरिवर्तन तब विशिष्ट रूप से एक पथ से मेल खाता है अधूरा कश्मीर जिस तरह से पेड़।

क्रमपरिवर्तन की अद्वितीय संख्या तो कश्मीर-ary पेड़ टर्मिनल नोड्स के बाद आदेश ट्रावर्सल में पेड़-नोड के सूचकांक से मेल खाती है।

सौभाग्य से, हम वास्तव में पेड़ के ट्रैवर्सल को निष्पादित नहीं करना है - हमें केवल यह जानने की जरूरत है कि पेड़ में कितने टर्मिनल नोड लेक्सिकोग्राफिक रूप से कम हमारे नोड से हैं।पेड़ में किसी नोड पर गणना करना बहुत आसान है, से नीचे टर्मिनल नोड्स वर्तमान नोड अनुक्रम में अप्रयुक्त तत्वों का उपयोग करके क्रमपरिवर्तन की संख्या के बराबर है, जिसमें एक बंद फॉर्म समाधान है जो एक साधारण है फैक्ट्रोरियल का गुणा।

तो हमारे 6 मूल पत्र दिए गए हैं, और हमारे क्रमपरिवर्तन का पहला तत्व एक 'बी' है, हम निर्धारित करते हैं कि 5 होगा!/3! 1! 1! = 20 तत्व जो 'ए' से शुरू हुए, इसलिए हमारा क्रमपरिवर्तन संख्या 20 से अधिक होनी चाहिए। अगर हमारा पहला पत्र 'सी' था, तो हम इसे 5 के रूप में गणना कर सकते थे!/2! 2! 1! (ए नहीं) + 5!/3! 1! 1! (बी नहीं) = 30+ 20, या वैकल्पिक रूप से 60 (कुल) - 5!/3! 2! 0! (सी) = 50

इसका उपयोग करके, हम क्रमपरिवर्तन (जैसे 'बीएएबीसीए') ले सकते हैं और निम्नलिखित गणनाएं कर सकते हैं: पर्म्यूशन # = (5!/2! 2! 1!) ('बी') + 0 ('ए') + 0 ('ए') + 3!/1! 1! 1! ('बी') + 2!/1!

= 30 + 3 +2 = 35

जांच की जा रही है कि इस काम करता है: CBBAAA

(5/2 से मेल खाती है 2 1 (नहीं एक) + 5/3 1!!!!! 1! (बी नहीं)) 'सी' + 4!/2! 2! 0! (ए नहीं) 'बी' + 3!/2! 1! 0! (ए नहीं) 'बी' = (30 + 20) +6 + 3 = 59

इसी तरह, एएएबीबीसी = 0 ('ए') + 0 'ए' + '0' ए '+ 0' बी ' + 0 'बी' + 0 'सी = 0

नमूना कार्यान्वयन:

import math 
import copy 
from operator import mul 

def computePermutationNumber(inPerm, inCharClasses): 
    permutation=copy.copy(inPerm) 
    charClasses=copy.copy(inCharClasses) 

    n=len(permutation) 
    permNumber=0 
    for i,x in enumerate(permutation): 
     for j in xrange(x): 
      if(charClasses[j]>0): 
       charClasses[j]-=1 
       permNumber+=multiFactorial(n-i-1, charClasses) 
       charClasses[j]+=1 
     if charClasses[x]>0: 
      charClasses[x]-=1 
    return permNumber 

def multiFactorial(n, charClasses): 
    val= math.factorial(n)/ reduce(mul, (map(lambda x: math.factorial(x), charClasses))) 
    return val 

संख्या से क्रमपरिवर्तन में: इस प्रक्रिया को रिवर्स में किया जा सकता है, हालांकि मुझे यकीन है कि नहीं कर रहा हूँ कुशलता से कैसे: को देखते हुए एक क्रमपरिवर्तन संख्या, और वर्णमाला जो इसे उत्पन्न किया गया था, शेष क्रमपरिवर्तन संख्या से कम या उसके बराबर नोड्स की सबसे बड़ी संख्या घटाना।

उदा। 59 की क्रमपरिवर्तन संख्या को देखते हुए, हम पहले 30 + 20 = 50 ('सी') को छोड़कर 9 घटा सकते हैं। फिर हम 'बी' (6) और दूसरा 'बी' (3) घटा सकते हैं, हमारे मूल क्रमपरिवर्तन को फिर से उत्पन्न कर सकते हैं ।

Answer 2

क्रमपरिवर्तन के लिए एक नंबर मानचित्रण के लिए एक बहुत ही सरल एल्गोरिथ्म n अंक होते हैं

number<-digit[0]*10^(n-1)+digit[1]*10^(n-2)+...+digit[n]*10^0 

आप एल्गोरिदम क्रमपरिवर्तन उत्पन्न करने के लिए के लिए संसाधनों के बहुत सारे मिल सकते हैं। मुझे लगता है कि आप जैव सूचना विज्ञान में इस एल्गोरिदम का उपयोग करना चाहते हैं। उदाहरण के लिए आप पायथन से itertools.permutations का उपयोग कर सकते हैं।

Answer 3

परिणामस्वरूप संख्या एक शब्द (उदा। 32 या 64 बिट पूर्णांक) के अंदर अपेक्षाकृत आसानी से मानती है, तो अधिकतर लिंक किए गए लेख अभी भी लागू होते हैं। एक परिवर्तनीय आधार से एन्कोडिंग और डिकोडिंग वही रहता है। क्या परिवर्तन बदलता है यह कैसे बदलता है।

यदि आप अनुक्रम का क्रमपरिवर्तन बना रहे हैं, तो आप प्रतीकों की अपनी बाल्टी (मूल अनुक्रम से) से एक आइटम निकालते हैं और इसे शुरुआत में डाल देते हैं। फिर आप प्रतीकों की अपनी बाल्टी से एक और वस्तु चुनते हैं और इसे इसके अंत में डाल देते हैं। जब तक आप अपनी बाल्टी में प्रतीकों से बाहर नहीं निकलेंगे तब तक आप अंत में प्रतीकों को उठाकर रखेंगे।

महत्वपूर्ण बात यह है कि आपने प्रत्येक बार शेष प्रतीकों की बाल्टी से कौन सा आइटम चुना है। शेष प्रतीकों की संख्या कुछ ऐसा है जो आपको रिकॉर्ड करने की आवश्यकता नहीं है क्योंकि आप गणना कर सकते हैं जैसे कि आप क्रमपरिवर्तन बनाते हैं - यह आपके विकल्पों का नतीजा है, न कि विकल्प स्वयं।

यहां दी गई रणनीति आपके द्वारा चुने गए रिकॉर्ड को रिकॉर्ड करने के लिए है, और फिर चुने जाने के लिए छोड़ी गई चीज़ों की एक सरणी प्रस्तुत करें। फिर चुनें, रिकॉर्ड करें कि आपने कौन सी इंडेक्स चुना है (वैरिएबल बेस विधि के माध्यम से इसे पैक करना), और दोहराने तक कुछ भी नहीं छोड़ा जाता है। (जैसा कि आप ऊपर अनुक्रमित अनुक्रम बना रहे थे।)

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

के एक संकेतन है कि इस स्पष्ट करता है अपनाने करते हैं: c-2 a-3 b-1:

इसके बजाय डुप्लिकेट प्रतीकों हमारे बाल्टी में छोड़ दिया चुनने के लिए लिस्टिंग के c a b c a a तरह से हम उनके साथ कितने अभी भी बाल्टी में हैं साथ सूचीबद्ध करेंगे।

ध्यान दें कि यदि आप सूची में c चुनते हैं, तो बाल्टी में c-1 a-3 b-1 है। इसका मतलब है कि अगली बार जब हम कुछ चुनते हैं, तो हमारे पास तीन विकल्प हैं।

लेकिन दूसरी तरफ, यदि मैंने सूची में b चुना है, तो बाल्टी में c-2 a-3 शेष है। इसका मतलब है कि अगली बार जब हम कुछ चुनते हैं, तो हमारे पास केवल दो विकल्प होते हैं।

अनुक्रमित अनुक्रम का पुनर्निर्माण करते समय हम केवल बाल्टी को उसी तरह बनाए रखते हैं जब हम क्रमपरिवर्तन संख्या की गणना कर रहे थे।

कार्यान्वयन विवरण मामूली नहीं हैं, लेकिन वे मानक एल्गोरिदम के साथ सीधा हैं। एकमात्र चीज जो आपको परेशान कर सकती है वह तब करना है जब आपकी बाल्टी में कोई प्रतीक उपलब्ध न हो।

मान लीजिए कि आपकी बाल्टी को जोड़े (जैसे ऊपर) की सूची द्वारा दर्शाया गया था: c-1 a-3 b-1 और आप c चुनते हैं। आपकी परिणामी बाल्टी c-0 a-3 b-1 है। लेकिन c-0 अब कोई विकल्प नहीं है, इसलिए आपकी सूची में केवल दो प्रविष्टियां होंगी, न कि तीन। आप पूरी सूची को 1 से नीचे ले जा सकते हैं जिसके परिणामस्वरूप a-3 b-1 हो सकता है, लेकिन यदि आपकी सूची लंबी है तो यह महंगा है। एक तेज़ एक आसान समाधान: बाल्टी के अंतिम तत्व को हटाए गए स्थान में ले जाएं और अपनी बाल्टी आकार घटाएं: c0 a-3 b-1b-1 a-3 <empty> या बस b-1 a-3 बन जाता है।

ध्यान दें कि हम उपरोक्त कार्य कर सकते हैं क्योंकि इससे कोई फर्क नहीं पड़ता कि बाल्टी में प्रतीकों को किस क्रम में सूचीबद्ध किया गया है, जब तक यह वही तरीका है जब हम संख्या को एन्कोड या डीकोड करते हैं।

Answer 4

यहां जावा में एक एल्गोरिदम है जो अनुक्रम के पूर्णांक को मैप करके संभावित अनुक्रमों का आकलन करता है।

public class Main { 

    private int[] counts = { 3, 2, 1 }; // 3 Symbols A, 2 Symbols B, 1 Symbol C 
    private int n = sum(counts); 

    public static void main(String[] args) { 
     new Main().enumerate(); 
    } 

    private void enumerate() { 
     int s = size(counts); 
     for (int i = 0; i < s; ++i) { 
      String p = perm(i); 
      System.out.printf("%4d -> %s\n", i, p); 
     } 

    } 

    // calculates the total number of symbols still to be placed 
    private int sum(int[] counts) { 
     int n = 0; 
     for (int i = 0; i < counts.length; i++) { 
      n += counts[i]; 
     } 
     return n; 
    } 

    // calculates the number of different sequences with the symbol configuration in counts 
    private int size(int[] counts) { 
     int res = 1; 
     int num = 0; 
     for (int pos = 0; pos < counts.length; pos++) { 
      for (int den = 1; den <= counts[pos]; den++) { 
       res *= ++num; 
       res /= den; 
      } 
     } 
     return res; 
    } 

    // maps the sequence number to a sequence 
    private String perm(int num) { 
     int[] counts = this.counts.clone(); 
     StringBuilder sb = new StringBuilder(n); 
     for (int i = 0; i < n; ++i) { 
      int p = 0; 
      for (;;) { 
       while (counts[p] == 0) { 
        p++; 
       } 
       counts[p]--; 
       int c = size(counts); 
       if (c > num) { 
        sb.append((char) ('A' + p)); 
        break; 
       } 
       counts[p]++; 
       num -= c; 
       p++; 
      } 
     } 
     return sb.toString(); 
    } 

} 

एल्गोरिदम द्वारा उपयोग किया जाने वाला मानचित्रण निम्नानुसार है। मैं इसे चित्रित करने के लिए प्रश्न (3 एक्स ए, 2 एक्स बी, 1 एक्स सी) में दिए गए उदाहरण का उपयोग करता हूं।

कुल 60 (= 6!/3!/2!/1!) कुल अनुक्रमों में 30, = 5!/2!/2!/1!) उनमें से A पहले स्थान पर हैं , 20 (= 5!/3!/1!/1!) पहले स्थान पर B है, और 10 (= 5!/3!/2!/0!) पहले स्थान पर C है।

संख्या 0..29 एक A के साथ शुरू सभी दृश्यों से मैप किया जाता 30..49 B के साथ शुरू दृश्यों का उल्लेख किया जाता है, और 50..59 C के साथ शुरू दृश्यों को मैप किया जाता है।

एक ही प्रक्रिया 19 (= 49-30), उदाहरण के लिए क्रम में अगला जगह के लिए दोहराया है, हम ले दृश्यों B के साथ शुरू हम अब संख्या 0 (= 30-30) मैप करने के लिए .. विन्यास के साथ दृश्यों (3 एक्स ए, 1 x बी, 1 x सी)