找到一个给定的排列的索引(Finding the index of a given permutat

我读的数字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 ，具有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个项目选择中的K组唯一组合的问题。

我已经写在C＃中的类来处理常见的功能与二项式系数工作。它执行以下任务：

输出在一个不错的格式，所有的K-指标对任意n取K到一个文件中。的K-索引可以用更多的描述字符串或字母被取代。
的K-索引来在排序二项式系数表中的条目的适当词典索引或秩转换。这种技术比依赖于旧的迭代公开的技术快得多。它通过使用帕斯卡三角固有的数学特性做到这一点，并与遍历集合是非常有效的。
以排序二项式系数表，以相应的K-索引索引转换。我相信这是比年长的迭代解决方案快。
使用马克Dominus法计算二项式系数，这是不太可能溢出，并用较大的数字作品。
该类.NET编写C＃和提供了一种通过使用泛型列表管理相关的问题（如果有的话）的对象。这个类的构造函数叫做InitTable，当真正将创建一个泛型列表保存到被管理的对象bool值。如果这个值是假的，那么它不会创建表。该表不需要为了使用上述4种方法来产生。提供存取方法来访问表。
有一个相关的测试类，它展示了如何使用类及其方法。它有2案件中广泛的测试，有没有已知的错误。

要了解这个类，并下载代码，请参阅Tablizing二项式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 3:

有N！排列。为了表示你至少需要N位指数。

Answer 4:

这里是一个办法做到这一点，如果你想假定算术运算是恒定的时间：

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 5:

有一个Java的解决方案，在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) )