使用堆算法生成排列

我正在尝试使用我在维基百科中找到的堆算法生成数组的所有排列。

这是我到目前为止所尝试的：

n <- 3
A <- c(1, 2, 3)
perm <- function(n, A) {
  if (n == 1)
    print(perm)
  for (i in length(A))
    perm(n, A - 1) 
  if (A %% 2 == 1) {
    swap(A[i], A[n - 1])
  } else {
    swap(A[0], A[n - 1])
  } 
}
perm(3, A)

输出未显示，如果能得到一些帮助就太好了。

9除了一些名称误用之外，所提供的代码还存在四个基本问题：

1. 维基百科中 Heap 算法的实现假设0-based索引，而 R 的向量是1-based. So A[0]需要翻译成A[1]（即数组中的第一个元素），而A[n-1]需要翻译成A[n]（这是最后一个元素n-前缀A).

2. 令人惊讶的是，该代码并不遵循维基百科代码的迭代结构。剥离其本质，正确的代码是（更改为基于 1 的索引）：

   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 算法满足的“格雷码”要求的本质。

3. 各种伪代码实现（以及 Python 中的具体实现）假设数组参数实际上是通过引用传递的，因此递归调用中的交换对调用者是可见的。但是 R 传递数组value，因此每个递归调用都有自己的数组实例，并且修改不会反映在调用者的数组中。

4. 交换的计算如下：

   • If n甚至，A[n]被交换为A[1].
   • If n是奇数，A[n]被交换为A[i].

   （请记住，循环限制是n - 1, not n, and 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）；
• 每个生成的排列都是唯一的；
• 两个连续的排列仅在一次交换中不同。

验证所有这三个条件将避免堆算法实现中最常见的错误。

以下是上述 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