我正在嘗試使用我在維基百科中找到的堆演算法生成陣列的所有排列。
這是我到目前為止嘗試過的：
n <- 3
array <- c(1, 2, 3)
perm <- function(n, array) {
if (n == 1)
print(perm)
for (i in length(array))
perm(n, array - 1)
if (array %% 2 == 1) {
swap(array[i], array[n - 1])
} else {
swap(array[0], array[n - 1])
}
}
perm(3, array)
輸出沒有顯示，如果能得到一些幫助會很棒。
uj5u.com熱心網友回復：
除了一些濫用名稱之外，所提供的代碼還有四個基本問題：
維基百科中堆演算法的實作假定索引是基于 0 的，而 R 的向量是基于 1 的。so
array[0]需要轉換為array[1]（即陣列的第一個元素），whilearray[n-1]需要轉換為array[n]（陣列的n前綴中的最后一個元素。（另外，array作為變數名使用也是不明智的）在 R 中，因為它是一個預定義的名稱。）出人意料的是，代碼不遵循維基百科代碼的迭代結構。剝離其本質，正確的代碼是（更改為基于 1 的索引，并呼叫陣列
A）：define heap(A, n): if n == 1: process A else: for i from 1 to n - 1: ## Note the n - 1 heap(A, n - 1) ## Recurse swap A[n] with ... ## Swap end for heap(A, n - 1) ## Recurse end if這個回圈的重要方面是交換是在遞回之間完成的，既不是之前也不是之后。所以有
n遞回呼叫（假設n > 1）但只有n - 1交換。結果是兩個連續排列之間恰好有一次交換，這是 Heap 演算法滿足的“格雷碼”要求的本質。各種偽代碼實作（以及 Python 中的具體實作）假定陣列引數實際上是通過參考傳遞的，因此呼叫者可以看到遞回呼叫中的交換。但是 R 按值傳遞陣列，所以每個遞回呼叫都有它自己的陣列實體，并且修改不會反映在呼叫者的陣列中。
交換的計算如下：
- 如果
n是偶數，A[n]則與 交換A[1]。 - 如果
n是奇數，A[n]則與 交換A[i]。
（請記住，回圈限制是
n - 1，不是n，并且n總是大于 1。所以A[n]永遠不會與自身交換。）提供的代碼倒退了這一點。
- 如果
為了解決在每次遞回呼叫時復制陣列的問題，我們可以使用包含陣列的閉包；遞回呼叫的唯一引數是前綴長度。但請注意，在閉包環境中修改陣列需要我們使用<<-運算子。
heap_perm <- function(A) {
h <- function(n) {
if (n == 1) {
print(A)
} else {
h(n - 1)
for (i in 1:(n - 1)) {
if (n %% 2 == 1) pivot <- 1 else pivot <- i
tmp <- A[n]; A[n] <<- A[pivot]; A[pivot] <<- tmp
h(n - 1)
}
}
}
h(length(A))
}
在測驗 Heap 演算法的實作時，使用至少 4 個元素的向量很重要。（一個好的測驗會使用更大的向量，但四個是一個好的開始。）檢查輸出時，您需要檢查：
- 產生正確數量的排列（在 4 個元素的向量的情況下為 24）；
- 每個生成的排列都是唯一的；
- 兩個連續的排列僅在一次交換中不同。驗證所有這三個條件將避免 Heap 演算法實作中最常見的錯誤。
下面是上述 R 程式的測驗輸出：
> heap_perm(0:3)
[1] 0 1 2 3
[1] 1 0 2 3
[1] 2 0 1 3
[1] 0 2 1 3
[1] 1 2 0 3
[1] 2 1 0 3
[1] 3 1 0 2
[1] 1 3 0 2
[1] 0 3 1 2
[1] 3 0 1 2
[1] 1 0 3 2
[1] 0 1 3 2
[1] 0 2 3 1
[1] 2 0 3 1
[1] 3 0 2 1
[1] 0 3 2 1
[1] 2 3 0 1
[1] 3 2 0 1
[1] 3 2 1 0
[1] 2 3 1 0
[1] 1 3 2 0
[1] 3 1 2 0
[1] 2 1 3 0
[1] 1 2 3 0
uj5u.com熱心網友回復：
要在 R 中實作堆演算法，這應該有效：
h <- function(s, n) {
## processes Heap's algorithm
if (n == 1L) {
print(s)
} else {
h(s, n - 1L)
for (i in 1:(n - 1L)) {
if (n %% 2L == 0L) {
j <- 1L
} else {
j <- i
}
tmp <- s[n]
s[n] <- s[j]
s[j] <- tmp
h(s, n - 1L)
}
}
}
hperm <- function(A) {
## wrapper
h(A, length(A))
}
A <- 0:2
hperm(A)
# [1] 0 1 2
# [1] 1 0 2
# [1] 2 1 0
# [1] 1 2 0
# [1] 2 0 1
# [1] 0 2 1
主要是，你混了array，并n在條件（并swap()在基礎研發設施不存在）。
另請參見： 此Python代碼的堆演算法堆疊溢位。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400684.html
下一篇：排序陣列中的二分查找