इंडेक्सिंग अन्य रैंकिंग क्रमपरिवर्तन

Question

में रैंकिंग क्रमशः क्रमशः 0, ..., एन-1 लेक्सिकोग्राफिक क्रम में सभी पर विचार कर रहा है। मुझे दो रैंक दिए गए हैं, मैं और जे, और क्रमपरिवर्तन के पद को खोजने के लिए कहा है जो i'th क्रमपरिवर्तन के लिए क्रमपरिवर्तन लागू करने के परिणामस्वरूप है।

के लिए n = 3 कुछ उदाहरण:

पी (3) = [1, 2, 0], पी (4) = [2, 0, 1], परिणाम = [0, 1, 2 ], रैंक = 0

को देखते हुए मैं = j = 4, हम मिल [2, 0, 1] खुद के लिए आवेदन किया है [1, 2, 0], रैंक = 3.

क्या मैं आए हैं अब तक: मैं रैंक को लेमर कोड के माध्यम से अपने संबंधित क्रमपरिवर्तनों में परिवर्तित करता हूं, वांछित क्रमपरिवर्तन की गणना करता हूं, और लेहमेर कोड के माध्यम से रैंक में वापस परिवर्तित करता हूं।

क्या कोई भी वास्तव में क्रमपरिवर्तन की गणना किए बिना, अन्य दो रैंकों से वांछित क्रमपरिवर्तन के रैंक प्राप्त करने का कोई तरीका सुझा सकता है? एन भंडारण! एक्स एन! सरणी एक विकल्प नहीं है।

-edit- ध्यान दें कि यदि मैं कुछ अन्य आदेश सक्षम करता हूं तो मुझे लेक्सिकोग्राफिक आदेश से शादी नहीं हुई है।

-edit- यहां एन हैं! एन द्वारा! लेक्सिकोग्राफिक रैंक के लिए n = 3 & 4 के लिए ग्रिड। पंक्ति मुझे आउटपुट प्राप्त करने के लिए कॉलम जे में अनुक्रमित किया गया है। ध्यान दें कि एन = 3 ग्रिड एन = 4 ग्रिड के ऊपरी-बाएं कोने के समान है।

00|01|02|03|04|05| 
01|00|03|02|05|04| 
02|04|00|05|01|03| 
03|05|01|04|00|02| 
04|02|05|00|03|01| 
05|03|04|01|02|00| 

00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|20|21|22|23| 
01|00|03|02|05|04|07|06|09|08|11|10|13|12|15|14|17|16|19|18|21|20|23|22| 
02|04|00|05|01|03|08|10|06|11|07|09|14|16|12|17|13|15|20|22|18|23|19|21| 
03|05|01|04|00|02|09|11|07|10|06|08|15|17|13|16|12|14|21|23|19|22|18|20| 
04|02|05|00|03|01|10|08|11|06|09|07|16|14|17|12|15|13|22|20|23|18|21|19| 
05|03|04|01|02|00|11|09|10|07|08|06|17|15|16|13|14|12|23|21|22|19|20|18| 
06|07|12|13|18|19|00|01|14|15|20|21|02|03|08|09|22|23|04|05|10|11|16|17| 
07|06|13|12|19|18|01|00|15|14|21|20|03|02|09|08|23|22|05|04|11|10|17|16| 
08|10|14|16|20|22|02|04|12|17|18|23|00|05|06|11|19|21|01|03|07|09|13|15| 
09|11|15|17|21|23|03|05|13|16|19|22|01|04|07|10|18|20|00|02|06|08|12|14| 
10|08|16|14|22|20|04|02|17|12|23|18|05|00|11|06|21|19|03|01|09|07|15|13| 
11|09|17|15|23|21|05|03|16|13|22|19|04|01|10|07|20|18|02|00|08|06|14|12| 
12|18|06|19|07|13|14|20|00|21|01|15|08|22|02|23|03|09|10|16|04|17|05|11| 
13|19|07|18|06|12|15|21|01|20|00|14|09|23|03|22|02|08|11|17|05|16|04|10| 
14|20|08|22|10|16|12|18|02|23|04|17|06|19|00|21|05|11|07|13|01|15|03|09| 
15|21|09|23|11|17|13|19|03|22|05|16|07|18|01|20|04|10|06|12|00|14|02|08| 
16|22|10|20|08|14|17|23|04|18|02|12|11|21|05|19|00|06|09|15|03|13|01|07| 
17|23|11|21|09|15|16|22|05|19|03|13|10|20|04|18|01|07|08|14|02|12|00|06| 
18|12|19|06|13|07|20|14|21|00|15|01|22|08|23|02|09|03|16|10|17|04|11|05| 
19|13|18|07|12|06|21|15|20|01|14|00|23|09|22|03|08|02|17|11|16|05|10|04| 
20|14|22|08|16|10|18|12|23|02|17|04|19|06|21|00|11|05|13|07|15|01|09|03| 
21|15|23|09|17|11|19|13|22|03|16|05|18|07|20|01|10|04|12|06|14|00|08|02| 
22|16|20|10|14|08|23|17|18|04|12|02|21|11|19|05|06|00|15|09|13|03|07|01| 
23|17|21|11|15|09|22|16|19|05|13|03|20|10|18|04|07|01|14|08|12|02|06|00| 

यहां एन = 4 के लिए कारक हैं। मैंने कॉम्पैक्टनेस के लिए अंतिम अंक छोड़ा, जो हमेशा शून्य होता है।

000|001|010|011|020|021|100|101|110|111|120|121|200|201|210|211|220|221|300|301|310|311|320|321| 
001|000|011|010|021|020|101|100|111|110|121|120|201|200|211|210|221|220|301|300|311|310|321|320| 
010|020|000|021|001|011|110|120|100|121|101|111|210|220|200|221|201|211|310|320|300|321|301|311| 
011|021|001|020|000|010|111|121|101|120|100|110|211|221|201|220|200|210|311|321|301|320|300|310| 
020|010|021|000|011|001|120|110|121|100|111|101|220|210|221|200|211|201|320|310|321|300|311|301| 
021|011|020|001|010|000|121|111|120|101|110|100|221|211|220|201|210|200|321|311|320|301|310|300| 
100|101|200|201|300|301|000|001|210|211|310|311|010|011|110|111|320|321|020|021|120|121|220|221| 
101|100|201|200|301|300|001|000|211|210|311|310|011|010|111|110|321|320|021|020|121|120|221|220| 
110|120|210|220|310|320|010|020|200|221|300|321|000|021|100|121|301|311|001|011|101|111|201|211| 
111|121|211|221|311|321|011|021|201|220|301|320|001|020|101|120|300|310|000|010|100|110|200|210| 
120|110|220|210|320|310|020|010|221|200|321|300|021|000|121|100|311|301|011|001|111|101|211|201| 
121|111|221|211|321|311|021|011|220|201|320|301|020|001|120|101|310|300|010|000|110|100|210|200| 
200|300|100|301|101|201|210|310|000|311|001|211|110|320|010|321|011|111|120|220|020|221|021|121| 
201|301|101|300|100|200|211|311|001|310|000|210|111|321|011|320|010|110|121|221|021|220|020|120| 
210|310|110|320|120|220|200|300|010|321|020|221|100|301|000|311|021|121|101|201|001|211|011|111| 
211|311|111|321|121|221|201|301|011|320|021|220|101|300|001|310|020|120|100|200|000|210|010|110| 
220|320|120|310|110|210|221|321|020|300|010|200|121|311|021|301|000|100|111|211|011|201|001|101| 
221|321|121|311|111|211|220|320|021|301|011|201|120|310|020|300|001|101|110|210|010|200|000|100| 
300|200|301|100|201|101|310|210|311|000|211|001|320|110|321|010|111|011|220|120|221|020|121|021| 
301|201|300|101|200|100|311|211|310|001|210|000|321|111|320|011|110|010|221|121|220|021|120|020| 
310|210|320|110|220|120|300|200|321|010|221|020|301|100|311|000|121|021|201|101|211|001|111|011| 
311|211|321|111|221|121|301|201|320|011|220|021|300|101|310|001|120|020|200|100|210|000|110|010| 
320|220|310|120|210|110|321|221|300|020|200|010|311|121|301|021|100|000|211|111|201|011|101|001| 
321|221|311|121|211|111|320|220|301|021|201|011|310|120|300|020|101|001|210|110|200|010|100|000| 

Answer 1

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

Initialize: 
p = input permutation 
q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n) 
n = length(p) 

rank(n, p, q) 
    if n=1 then return 0 fi 
    s = p[n-1] 
    swap(p[n-1], p[q[n-1]]) 
    swap(q[s], q[n-1]) 
    return s + n * rank(n-1, p, q) 
end 

स्यूडोकोड है कि:

सबसे पहले, (क्रमपरिवर्तन में पद से जाना)

Initialize: 
n = length(permutation) 
r = desired rank 
p = identity permutation of n elements [0, 1, ..., n] 

unrank(n, r, p) 
    if n > 0 then 
    swap(p[n-1], p[r mod n]) 
    unrank(n-1, floor(r/n), p) 
    fi 
end 

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

इनमें से दोनों का चलने का समय ओ (एन) है।

वहाँ एक अच्छा, पठनीय कागज का कारण बताते हुए इस काम करता है: रैंकिंग & Unranking परम्युटेशन्स रैखिक समय में, Myrvold & Ruskey, सूचना प्रोसेसिंग पत्र वॉल्यूम 79, अंक 6, 30 सितंबर 2001, पेज 281-284 से।

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Answer 2

हैं, आर के अलावा, आप या तो एक विशेष पी करने के लिए शादी-शुदा नहीं कर रहे हैं, हम एक संभावित जवाब की सुविधा के लिए परिवर्तन समारोह को फिर से परिभाषित कर सकता है। फ़ंक्शन, newPerm, नीचे एक समान स्थिरता के साथ आर के संबंध में एक सूची को अनुमति देगा क्योंकि "अनुक्रमित"।

नीचे दिया गया उदाहरण दक्षता के लिए अनुकूलित नहीं है (उदाहरण के लिए, रैंकिंग/अनैंकिंग ओ (एन) में किया जा सकता है)। आउटपुट की आखिरी दो पंक्तियां "इंडेक्सिंग" परमिट फ़ंक्शन को फिर से परिभाषित करने की अनुमति देती हैं - जैसा कि आप देख सकते हैं, वे दोनों क्रमपरिवर्तन सेट पर मैप किए जाने पर समान क्रमिक क्रमों को उत्पन्न करते हैं। समारोह, f, प्रश्न का उत्तर होगा।

हास्केल कोड:

import Data.List (sort,permutations) 
import Data.Maybe (fromJust) 

sortedPermutations = sort $ permutations [0,1,2,3,4,5,6] 

rank p = fromJust (lookup p rs) where rs = zip sortedPermutations [0..] 

unrank r = fromJust (lookup r ps) where ps = zip [0..] sortedPermutations 

tradPerm p s = foldr (\a b -> s!!a : b) [] p 

newPerm p s = unrank (f (rank p) (rank s)) 

f r1 r2 = let l = r1 - r2 in if l < 0 then length sortedPermutations + l else l 

आउटपुट:

*Main Data.List> unrank 3 
[0,1,2,3,5,6,4] 

*Main Data.List> unrank 8 
[0,1,2,4,5,3,6] 

*Main Data.List> f 3 8 
5035 

*Main Data.List> newPerm [0,1,2,3,5,6,4] [0,1,2,4,5,3,6] 
[6,5,4,3,0,2,1] 

*Main Data.List> rank [6,5,4,3,0,2,1] 
5035 

*Main Data.List> length $ group $ sort $ map (tradPerm [1,2,5,0,4,3,6]) sortedPermutations 
5040 

*Main Data.List> length $ group $ sort $ map (newPerm [1,2,5,0,4,3,6]) sortedPermutations 
5040