查找給定排列的索引

Question

我正在以某種順序逐一讀取數字0, 1, ..., (N - 1)。我的目標是找到給定排列的詞典索引，僅使用O(1)空間。

以前曾詢問過這個問題，但是我能找到的所有算法都使用O(N)的空間。我開始認爲這是不可能的。但是減少分配的數量對我來說真的很有幫助。

Answer 1

考慮以下數據：

chars = [a, b, c, d] 
perm = [c, d, a, b] 
ids = get_indexes(perm, chars) = [2, 3, 0, 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)在太空中，考慮到初始列表作爲一個不變的成本;並且它要求O(N)及時，考慮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

有N個排列爲代表指數你至少需要N位

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 

我故意寫出來一定的計算方法，能更簡單地使用一些Python內建的操作來完成，但我想讓它更加明顯，目前正在使用的空間沒有多餘的非恆定的量。

正如maxim1000指出的那樣，表示結果所需的位數會隨着n的增加而快速增長，因此最終需要大整數，而這些整數不再具有恆定時間的算術運算，但我認爲該代碼解決了你的問題。

Answer 4

如果您正在尋找一種方法來獲取單個組合的詞典索引或排名而不是排列，那麼您的問題將落入二項式係數之下。二項式係數處理選擇K組中的總共具有N項的獨特組合的問題。

我已經在C＃中編寫了一個類來處理使用二項式係數的常用函數。它執行以下任務：

1. 輸出所有的在一個不錯的格式K-索引的任意N型取K到一個文件中。 K-index可以用更多的描述性字符串或字母來代替。

2. 的K-索引來在排序二項式係數表中的條目的適當詞典索引或秩轉換。這種技術比依靠迭代的較早發佈的技術要快得多。它通過使用Pascal三角形中固有的數學屬性來實現這一點，並且與迭代該集合相比非常有效。

3. 以排序的二項式係數表，以相應的K-索引索引轉換。我相信它比以前的迭代解決方案更快。

4. 使用Mark Dominus方法來計算二項式係數，這是不太可能溢出和更大的數字作品。

5. 類是.NET編寫C＃和提供了一種通過使用泛型列表管理相關的問題（如果有的話）的對象。這個類的構造函數接受一個名爲InitTable的布爾值，當true時將創建一個通用列表來保存要管理的對象。如果此值爲false，則不會創建表。該表不需要創建，以使用上述4種方法。提供Accessor方法來訪問表。

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上有這個問題的java解決方案。它有一個很好的解釋，爲什麼它是真實的，代碼很容易遵循。 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

我只是直接使用Visual Basic和我的程序可以寫代碼計算每個索引或每個相應的排列對一個給定的索引最多17個元素（這個限制是由於我的編譯器超過17的數字的科學記數法的近似值）。

如果你有興趣，我可以，我可以發送程序或其他地方發佈下載。 它工作正常，它可以用於測試和典範代碼的輸出。

我用了James D. McCaffrey的方法叫做factoradic，你可以閱讀它here和其他東西here（在頁面末尾的討論中）。