如何从n个元素中找到k-置换的索引？

Question

我知道，对于大小k的k -permutation p，从n要素为基础，主要有：

P(n, k) = n!/(n - k)! 

可能k -permutations。例如：

k = 2 
n = 4 
l = [1, 2, 3, 4] 
P(n, k) = 4!/(4 - 2)! = 12 

1 2 | 2 1 | 3 1 | 4 1 
1 3 | 2 3 | 3 2 | 4 2 
1 4 | 2 4 | 3 4 | 4 3 

而另一个例子：

k = 3 
n = 4 
l = [1, 2, 3, 4] 
P(n, k) = 4!/(4 - 3)! = 24 

1 2 3 | 2 1 3 | 3 1 2 | 4 1 2 
1 2 4 | 2 1 4 | 3 1 4 | 4 1 3 
1 3 2 | 2 3 1 | 3 2 1 | 4 2 1 
1 3 4 | 2 3 4 | 3 2 4 | 4 2 3 
1 4 2 | 2 4 1 | 3 4 1 | 4 3 1 
1 4 3 | 2 4 3 | 3 4 2 | 4 3 2 

那么，如何才能找到的k -permutation p指数？考虑按照字典顺序生成的排列 。

编辑： 我可以通过寻找在其中“块” p是，通过寻址的p第一元件的块开始。例如，对于p = [3, 2, 4]，p的索引应该至少为12（从0到P(n, k) - 1）。

但是，为了找到那个“块”内的第二个元素，我必须看看剩下的项目是什么，以及它们将在哪个位置。我的意思是，我最终会在名单[1, 4]，而4将位于第2位，所以仅仅使用元素作为关键就需要一些额外的操作。

我可以使用散列来查找元素并更新它们的位置，但它会给我一个O(n^2)时间复杂度。有没有可能做得更好？

Answer 1

在给定位置给定数字的排列数由公式 （n位数位置）给出！ /（n-k）！其中数字位置从左侧开始为1.

要获得给定排列（即其索引）的前面排列的数目，请将每个数字的公式乘以尚未使用的前面数字的数字，并且把它们加起来。

实施例1中，k = 2，N = 4，P = [3,4]

第一位数字，3： （4-1）！ /（4-2）！*（未使用的前面的数字的数量，2）= 6 在第一个之前有六个排列，在第一个排列有3个排列。

第二个数字4： （4-2）！ /（4-2）！ *（未使用前述数字位数，2）= 2 有前述，在位置4具有第一两个置换2.

零的索引：6 + 2 = 8

实施例2中，k = 3，n = 4，p = [3,2,4]

第一位数字3： （4-1）！ /（4-3）！ *（未使用的前面的数字的数量，2）= 12 在第一个之前有12个排列，在第一个排列中有3个排列。

第二个数字2： （4-2）！ /（4-3）！ *（未使用的前面数字的数量，1）= 2 在第一个之前有两个排列，在第二个排列中有2个。

第三个数字4： （4-3）！ /（4-3）！ *（未使用的前述数字数，1）= 1 有前述，在位置4具有第一个置换3.

零基于指数：12 + 2 + 1 = 15。

Answer 2

TXR language：

$ txr -p "(pos '(1 4 3) (perm '(1 2 3 4) 3))" 
5 

这是蛮力，但是，当然pos对排列的结构一无所知。

Answer 3

使用binary search tree（BST）。在开始之前将所有数字存储在其中，并在使用之后将其删除。要找到第x个元素，请为每个顶点维护.subtreeSize，然后下降树以找到您需要的数字。伪代码：

def findXth(x): 
     curVertex = BST.root 
     while: 
      curPosition = curVertex.leftChild.subtreeSize 
      if curPosition == x: return curVertex.value 
      elif curPosition > x: curVertex = curVertex.leftChild 
      elif curPosition < x: curVertex = curVertex.rightChild 

不要忘记检查顶点的存在，并删除您找到顶点。

整体复杂度将是O（n log n）。

Answer 4

可以参考低于功能

/** 
* list all k or <=k size permutation of a given list with n unique elements. 
* n can be bigger than 64. this function will take O(K^N) time, Bad. 
* 
* @param uniqueList 
* @param permutationSize 
* @param permutation 
* @param only   Only show the permutation of permutationSize, 
*      else show all permutation of less than or equal to permutationSize. 
*/ 
public static void my_permutationOf(List<Integer> uniqueList, int permutationSize, List<Integer> permutation, boolean only) { 
    if (permutation == null) { 
     assert 0 < permutationSize && permutationSize <= uniqueList.size(); 
     permutation = new ArrayList<>(permutationSize); 
     if (!only) { 
      System.out.println(Arrays.toString(permutation.toArray())); 
     } 
    } 
    for (int i : uniqueList) { 
     if (permutation.contains(i)) { 
      continue; 
     } 
     permutation.add(i); 
     if (!only) { 
      System.out.println(Arrays.toString(permutation.toArray())); 
     } else if (permutation.size() == permutationSize) { 
      System.out.println(Arrays.toString(permutation.toArray())); 
     } 
     if (permutation.size() < permutationSize) { 
      my_permutationOf(uniqueList, permutationSize, permutation, only); 
     } 
     permutation.remove(permutation.size() - 1); 
    } 
} 

例如你能想到的元素是指数

public static void main(String[] args) throws Exception { 
    my_permutationOf(new ArrayList<Integer>() { 
     { 
      add(0); 
      add(1); 
      add(2); 
      add(3); 

     } 
    }, 3, null, true); 
} 

结果是

[0, 1, 2] 
[0, 1, 3] 
[0, 2, 1] 
[0, 2, 3] 
[0, 3, 1] 
[0, 3, 2] 
[1, 0, 2] 
[1, 0, 3] 
[1, 2, 0] 
[1, 2, 3] 
[1, 3, 0] 
[1, 3, 2] 
[2, 0, 1] 
[2, 0, 3] 
[2, 1, 0] 
[2, 1, 3] 
[2, 3, 0] 
[2, 3, 1] 
[3, 0, 1] 
[3, 0, 2] 
[3, 1, 0] 
[3, 1, 2] 
[3, 2, 0] 
[3, 2, 1]