algorithm - 查找给定排列的索引

Question

我0, 1, ..., (N - 1)以某种顺序一一阅读数字。我的目标是找到这个给定排列的词典索引，只使用O(1)空间。

之前有人问过这个问题，但是我能找到的所有算法都使用了O(N)空间。我开始认为这是不可能的。但这确实对我减少分配数量有很大帮助。

score 4 · Accepted Answer

考虑以下数据：

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;
    base = base / len;
    for (i = 0; i < length(perm); i++) {
        index += base * ids[i];
        base = base / len;
    }

}

这是一个伪代码，但它也很容易转换为任何语言（：

score 3 · Accepted Answer

如果您正在寻找一种方法来获取字典索引或唯一组合的排名而不是排列，那么您的问题属于二项式系数。二项式系数处理在总共有 N 个项目的 K 组中选择唯一组合的问题。

我用 C# 编写了一个类来处理处理二项式系数的常用函数。它执行以下任务：

将任何 N 选择 K 的所有 K 索引以良好的格式输出到文件。K-indexes 可以替换为更具描述性的字符串或字母。
将 K 索引转换为正确的词典索引或排序二项式系数表中条目的等级。这种技术比依赖迭代的旧已发布技术快得多。它通过使用帕斯卡三角形中固有的数学属性来做到这一点，并且与迭代集合相比非常有效。
将已排序二项式系数表中的索引转换为相应的 K 索引。我相信它也比旧的迭代解决方案更快。
使用Mark Dominus方法计算二项式系数，它不太可能溢出并且适用于更大的数字。
该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法。此类的构造函数采用一个名为 InitTable 的 bool 值，当它为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。无需创建表即可使用上述 4 种方法。提供了访问器方法来访问表。
有一个关联的测试类，它显示了如何使用该类及其方法。它已经用 2 个案例进行了广泛的测试，并且没有已知的错误。

要了解此类并下载代码，请参阅制表二项式系数。

以下测试代码将遍历每个唯一组合：

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 字节整数更大的字长。

score 1 · Accepted Answer

在 geekviewpoint 上有这个问题的 java 解决方案。它很好地解释了为什么它是正确的，并且代码很容易理解。http://www.geekviewpoint.com/java/numbers/permutation_index。它还有一个单元测试，可以使用不同的输入运行代码。

score 0 · Accepted Answer

0

有N个！排列。要表示索引，您至少需要 N 位。

于 2012-12-23T18:20:14.803 回答

score 0 · Accepted Answer

如果您想假设算术运算是常数时间，这是一种方法：

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 的增加而迅速增长，因此最终将需要大整数，它不再具有恒定时间算术，但我认为这段代码解决了您的问题的精神。

score 0 · Accepted Answer

我刚刚使用 Visual Basic 编写了一个代码，我的程序可以直接计算给定索引的每个索引或每个对应的排列，最多 17 个元素（这个限制是由于我的编译器的 17 以上数字的科学计数法的近似值）。

如果您有兴趣，我可以发送程序或将其发布到某个地方以供下载。它工作得很好，它可以用于测试和示范你的代码输出。

我使用了 James D. McCaffrey 的称为 factoradic 的方法，您可以在此处阅读有关它的内容，也可以在此处阅读（在页面末尾的讨论中）。

score 0 · Accepted Answer

这个想法没有什么新东西，而是一种完全矩阵化的方法，没有显式循环或递归（使用 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) )

algorithm - 查找给定排列的索引

7 回答 7

Related

Reference