查找给定排列的索引

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（在页面末尾的讨论中）。