किसी दिए गए क्रमपरिवर्तन

Question

की अनुक्रमणिका ढूँढना मैं कुछ क्रम में 0, 1, ..., (N - 1) नंबरों को पढ़ रहा हूं। मेरा लक्ष्य केवल O(1) स्थान का उपयोग करके, इस दिए गए क्रमपरिवर्तन की शब्दावली अनुक्रमणिका को ढूंढना है।

इस प्रश्न से पहले पूछा गया था, लेकिन सभी एल्गोरिदम मैं O(N) स्थान का उपयोग कर सकता था। मुझे लगता है कि यह संभव नहीं है। लेकिन यह वास्तव में आवंटन की संख्या को कम करने में बहुत मदद करेगा।

chars = [a, b, c, d] 
perm = [c, d, a, b] 
ids = get_indexes(perm, chars) = [2, 3, 0, 1] 

repetitions साथ क्रमचय के लिए सम्भावित समाधान हो जाता है इस प्रकार है::

Answer 1

निम्न डेटा को ध्यान में रखते

len = length(perm)   (len = 4) 
num_chars = length(chars) (len = 4) 

base = num_chars^len  (base = 4^4 = 256) 
base = base/len   (base = 256/4 = 64) 

id = base * ids[0]   (id = 64 * 2 = 128) 
base = base/len   (base = 64/4 = 16) 

id = id + (base * ids[1]) (id = 128 + (16 * 3) = 176) 
base = base/len   (base = 16/4 = 4) 

id = id + (base * ids[2]) (id = 176 + (4 * 0) = 176) 
base = base/len   (base = 4/4 = 1) 

id = id + (base * ids[3]) (id = 176 + (1 * 1) = 177) 

रिवर्स प्रक्रिया:

id = 177 
(id/(4^3)) % 4 = (177/64) % 4 = 2 % 4 = 2 -> chars[2] -> c 
(id/(4^2)) % 4 = (177/16) % 4 = 11 % 4 = 3 -> chars[3] -> d 
(id/(4^1)) % 4 = (177/4) % 4 = 44 % 4 = 0 -> chars[0] -> a 
(id/(4^0)) % 4 = (177/1) % 4 = 177 % 4 = 1 -> chars[1] -> b 

संभव की संख्या क्रमपरिवर्तनद्वारा दिया जाता है, जिसमें num_chars संभावित वर्णों की संख्या के रूप में है, और num_perm_digits क्रमपरिवर्तन में अंकों की संख्या के रूप में।

इसे स्थिर लागत के रूप में प्रारंभिक सूची पर विचार करते हुए अंतरिक्ष में O(1) की आवश्यकता होती है; और N पर विचार करते हुए O(N) की आवश्यकता होती है, क्योंकि आपके क्रमपरिवर्तन के अंकों की संख्या होगी।

ऊपर के चरणों के आधार पर, आप कर सकते हैं:

function identify_permutation(perm, chars) { 

    for (i = 0; i < length(perm); i++) { 
     ids[i] = get_index(perm[i], chars); 
    } 

    len = length(perm); 
    num_chars = length(chars); 

    index = 0; 
    base = num_chars^len - 1; 
    for (i = 0; i < length(perm); i++) { 
     index += base * ids[i]; 
     base = base/len; 
    } 

} 

यह एक स्यूडोकोड है, लेकिन यह भी किसी भी भाषा (कन्वर्ट करने के लिए काफी आसान है:।

Answer 2

एन रहे हैं क्रमपरिवर्तन सूचकांक का प्रतिनिधित्व करने के लिए आप कम से कम एन बिट्स की जरूरत

Answer 3

यहाँ यह करने के लिए यदि आप उस अंकगणितीय आपरेशनों लगातार समय कर रहे हैं ग्रहण करने के लिए चाहते हैं एक तरीका है:।

def permutationIndex(numbers): 
    n=len(numbers) 
    result=0 
    j=0 
    while j<n: 
    # Determine factor, which is the number of possible permutations of 
    # the remaining digits. 
    i=1 
    factor=1 
    while i<n-j: 
     factor*=i 
     i+=1 
    i=0 
    # Determine index, which is how many previous digits there were at 
    # the current position. 
    index=numbers[j] 
    while i<j: 
     # Only the digits that weren't used so far are valid choices, so 
     # the index gets reduced if the number at the current position 
     # is greater than one of the previous digits. 
     if numbers[i]<numbers[j]: 
     index-=1 
     i+=1 
    # Update the result. 
    result+=index*factor 
    j+=1 
    return result 

मैंने कुछ गणनाओं को उद्देश्य से लिखा है जो कि कुछ पायथन अंतर्निर्मित संचालन का उपयोग करके अधिक सरलता से किया जा सकता है, लेकिन मैं इसे और अधिक स्पष्ट करना चाहता था कि अंतरिक्ष की कोई अतिरिक्त निरंतर मात्रा का उपयोग नहीं किया जा रहा था।

अधिकतम 1000 नोट किया गया है, परिणाम का प्रतिनिधित्व करने के लिए आवश्यक बिट्स की संख्या तेजी से बढ़ेगी, इसलिए अंततः बड़े पूर्णांक की आवश्यकता होगी, जो अब निरंतर समय अंकगणित नहीं है, लेकिन मुझे लगता है कि यह कोड भावना की भावना को संबोधित करता है आपका प्रश्न।

Answer 4

यदि आप क्रमिक क्रम के बजाय लेक्सिकोग्राफिक इंडेक्स या अद्वितीय संयोजन के रैंक को प्राप्त करने का कोई तरीका ढूंढ रहे हैं, तो आपकी समस्या द्विपक्षीय गुणांक के अंतर्गत आती है। द्विपक्षीय गुणांक कुल एन वस्तुओं के साथ के समूहों में अद्वितीय संयोजन चुनने की समस्याओं को संभालता है।

मैंने द्विपक्षीय गुणांक के साथ काम करने के लिए सामान्य कार्यों को संभालने के लिए सी # में एक कक्षा लिखी है। यह निम्न कार्य करता है:

1. किसी भी एन के लिए एक अच्छा प्रारूप में सभी के-इंडेक्स आउटपुट को किसी फ़ाइल को के लिए चुनें। के-इंडेक्स को अधिक वर्णनात्मक तारों या अक्षरों के साथ प्रतिस्थापित किया जा सकता है।

2. के-इंडेक्स को उचित लेक्सिकोग्राफिक इंडेक्स या क्रमबद्ध बिनोमियल गुणांक तालिका में एक प्रविष्टि के रैंक में परिवर्तित करता है। यह तकनीक पुरानी प्रकाशित तकनीकों की तुलना में बहुत तेज है जो पुनरावृत्ति पर भरोसा करती है। यह पास्कल के त्रिभुज में अंतर्निहित गणितीय संपत्ति का उपयोग करके करता है और सेट पर पुनरावृत्ति की तुलना में बहुत ही कुशल है।

3. इंडेक्स को एक क्रमबद्ध बिनोमियल गुणांक तालिका में संबंधित के-इंडेक्स में परिवर्तित करता है। मेरा मानना ​​है कि यह पुराने पुनरावृत्तियों के समाधान से भी तेज है।

4. द्विपक्षीय गुणांक की गणना करने के लिए Mark Dominus विधि का उपयोग करता है, जो अतिप्रवाह होने की संभावना कम है और बड़ी संख्या में काम करता है।

5. कक्षा .NET C# में लिखा गया है और एक सामान्य सूची का उपयोग करके समस्या से संबंधित वस्तुओं (यदि कोई है) को प्रबंधित करने का एक तरीका प्रदान करता है। इस वर्ग के निर्माता को इटटेबल नामक एक बूल वैल्यू लेता है, जब सत्य ऑब्जेक्ट्स को प्रबंधित करने के लिए एक सामान्य सूची बनायेगा। यदि यह मान गलत है, तो यह तालिका नहीं बनाएगा। उपरोक्त 4 विधियों का उपयोग करने के लिए तालिका को बनाने की आवश्यकता नहीं है। तालिका तक पहुंचने के लिए एक्सेसर विधियां प्रदान की जाती हैं।

6. एक संबंधित टेस्ट क्लास है जो दिखाती है कि कक्षा और उसके तरीकों का उपयोग कैसे करें। इसका व्यापक रूप से 2 मामलों के साथ परीक्षण किया गया है और कोई ज्ञात बग नहीं है।

इस कक्षा के बारे में पढ़ने और कोड डाउनलोड करने के लिए, Tablizing The Binomial Coeffieicent देखें। अपनी पसंद की भाषा को काफी आसानी से

public void Test10Choose5() 
{ 
    String S; 
    int Loop; 
    int N = 10; // Total number of elements in the set. 
    int K = 5; // Total number of elements in each group. 
    // Create the bin coeff object required to get all 
    // the combos for this N choose K combination. 
    BinCoeff<int> BC = new BinCoeff<int>(N, K, false); 
    int NumCombos = BinCoeff<int>.GetBinCoeff(N, K); 
    // The Kindexes array specifies the indexes for a lexigraphic element. 
    int[] KIndexes = new int[K]; 
    StringBuilder SB = new StringBuilder(); 
    // Loop thru all the combinations for this N choose K case. 
    for (int Combo = 0; Combo < NumCombos; Combo++) 
    { 
     // Get the k-indexes for this combination. 
     BC.GetKIndexes(Combo, KIndexes); 
     // Verify that the Kindexes returned can be used to retrive the 
     // rank or lexigraphic order of the KIndexes in the table. 
     int Val = BC.GetIndex(true, KIndexes); 
     if (Val != Combo) 
     { 
     S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString(); 
     Console.WriteLine(S); 
     } 
     SB.Remove(0, SB.Length); 
     for (Loop = 0; Loop < K; Loop++) 
     { 
     SB.Append(KIndexes[Loop].ToString()); 
     if (Loop < K - 1) 
      SB.Append(" "); 
     } 
     S = "KIndexes = " + SB.ToString(); 
     Console.WriteLine(S); 
    } 
} 

आप इस वर्ग से अधिक बंदरगाह के लिए सक्षम होना चाहिए:

निम्नलिखित परीक्षण किया कोड प्रत्येक अद्वितीय संयोजन के माध्यम से पुनरावृति होगी। आपको अपने लक्ष्यों को पूरा करने के लिए शायद कक्षा के सामान्य भाग पर बंदरगाह नहीं करना पड़ेगा। जिन संयोजनों के साथ आप काम कर रहे हैं, उनकी संख्या के आधार पर, आपको 4 बाइट इनट्स की तुलना में एक बड़ा शब्द आकार का उपयोग करने की आवश्यकता हो सकती है।

Answer 5

geekviewpoint पर इस समस्या का जावा समाधान है। यह एक अच्छा स्पष्टीकरण है कि यह क्यों सच है और कोड का पालन करना आसान है। http://www.geekviewpoint.com/java/numbers/permutation_index। इसमें एक यूनिट टेस्ट भी है जो विभिन्न इनपुट के साथ कोड चलाता है।

Answer 6

कुछ भी नहीं है वास्तव में विचार में नए लेकिन कोई स्पष्ट पाश या प्रत्यावर्तन के साथ एक पूरी तरह से matricial विधि (Numpy लेकिन आसान अनुकूल करने के लिए उपयोग करते हुए):

import numpy as np 
import math 
vfact = np.vectorize(math.factorial, otypes='O') 

def perm_index(p): 
    return np.dot(vfact(range(len(p)-1, -1, -1)), 
        p-np.sum(np.triu(p>np.vstack(p)), axis=0)) 

Answer 7

मैं सिर्फ सीधे विजुअल बेसिक और मेरा कार्यक्रम कर सकते हैं का उपयोग कर एक कोड लिखा था 17 इंडेक्स तक दिए गए इंडेक्स को प्रत्येक इंडेक्स या प्रत्येक संबंधित क्रमपरिवर्तन की गणना करें (यह सीमा मेरे कंपाइलर के 17 से अधिक संख्याओं के वैज्ञानिक नोटेशन के अनुमान के कारण है)।

यदि आप रुचि रखते हैं तो मैं प्रोग्राम को भेज सकता हूं या इसे डाउनलोड के लिए कहीं भी प्रकाशित कर सकता हूं। यह ठीक काम करता है और यह आपके कोड के आउटपुट के परीक्षण और पैरागोन के लिए उपयोगी हो सकता है।

मैंने जेम्स डी। मैककैफ्रे की विधि का प्रयोग कारकैडिक कहा और आप इसके बारे में here और कुछ भी here (पृष्ठ के अंत में चर्चा में) पढ़ सकते हैं।