R：所有排列

Question

我正在尋找一個函數的第n表示

• 可以列出所有n！給定輸入向量的置換（通常只是序列1:n）
• 也可以僅列出所有n的前N個！排列

的第一個要求是從包gtools滿足，例如，通過從permn()包combinat，permutations()從包e1071，或permutations()。不過，我確信某些包還提供了另一個功能，也提供了第二個功能。我用過一次，但後來忘記了它的名字。

編輯： 「第一個N」的定義是任意的：該函數只需要一個內部枚舉方案，該方案總是被遵循，並且在N個排列被計算之後應該中斷。

正如Spacedman正確指出的那樣，至關重要的是函數不會計算比實際需要更多的排列（以節省時間）。

編輯 - 解決方案：我記得我使用的是numperm()來自包sna。 numperm(4, 7)給出元素1:4的第7個排列，對於第N個，必須循環。

Answer 1

這似乎是最好的方式來處理，這將是構建一個迭代可能產生排列的列表，而不是使用像permn一個函數，它前面生成的整個列表（昂貴的操作）。

在Python標準庫中的itertools模塊是尋找構建這些對象的指導的好地方。對於R，Itertools已部分重新實施，編號爲a package of the same name。

以下是使用的r itertools實施Python的發生器，對於排列創建的迭代器的一個端口的一個示例：

require(itertools) 

permutations <- function(iterable) { 
    # Returns permutations of iterable. Based on code given in the documentation 
    # of the `permutation` function in the Python itertools module: 
    # http://docs.python.org/library/itertools.html#itertools.permutations 
    n <- length(iterable) 
    indicies <- seq(n) 
    cycles <- rev(indicies) 
    stop_iteration <- FALSE 

    nextEl <- function(){ 
    if (stop_iteration){ stop('StopIteration', call. = FALSE) } 
    if (cycles[1] == 1){ stop_iteration <<- TRUE } # Triggered on last iteration 

    for (i in rev(seq(n))) { 
     cycles[i] <<- cycles[i] - 1 
     if (cycles[i] == 0){ 
     if (i < n){ 
      indicies[i:n] <<- c(indicies[(i+1):n], indicies[i]) 
     } 
     cycles[i] <<- n - i + 1 
     }else{ 
     j <- cycles[i] 
     indicies[c(i, n-j+1)] <<- c(indicies[n-j+1], indicies[i]) 
     return(iterable[indicies]) 
     } 
    } 
    } 

    # chain is used to return a copy of the original sequence 
    # before returning permutations. 
    return(chain(list(iterable), new_iterator(nextElem = nextEl))) 

} 

要錯誤引用Knuth：「在上面的代碼中的錯誤的當心;我只試過它，沒有證明它是正確的。「

對於序列1:10的前3個置換，permn支付巨大的代價計算不必要排列：

> system.time(first_three <- permn(1:10)[1:3]) 
    user system elapsed 
134.809 0.439 135.251 
> first_three 
[[1]] 
[1] 1 2 3 4 5 6 7 8 9 10 

[[2]] 
[1] 1 2 3 4 5 6 7 8 10 9 

[[3]] 
[1] 1 2 3 4 5 6 7 10 8 9) 

然而，通過permutations返回的迭代器，可以被詢問只有前三個備用大量計算的元素：

> system.time(first_three <- as.list(ilimit(permutations(1:10), 3))) 
    user system elapsed 
    0.002 0.000 0.002 
> first_three 
[[1]] 
[1] 1 2 3 4 5 6 7 8 9 10 

[[2]] 
[1] 1 2 3 4 5 6 7 8 10 9 

[[3]] 
[1] 1 2 3 4 5 6 7 9 8 10 

Python算法確實生成permuta tions的順序與permn不同。

計算所有排列仍然是可能的：

> system.time(all_perms <- as.list(permutations(1:10))) 
    user system elapsed 
498.601 0.672 499.284 

雖然更加昂貴，因爲Python的算法使得大量使用循環相比permn。 Python實際上在C中實現了這個算法，它補償瞭解釋循環的低效率。代碼可用in a gist on GitHub。如果有人有更好的主意，請轉走！

Answer 2

在我的R/combinat版本中，函數permn()長度超過三十行。一種方法是複製permn並將其更改爲提前停止。