如何從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]