使用堆的算法生成排列 [英] Generate Permutations using Heap's Algorithm

问题描述

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

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

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. 维基百科中堆算法的实现假定基于索引，而R的向量基于1。因此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通过值传递数组，因此每个递归调用都有自己的数组实例，并且修改不会反映在调用方的数组中。

4. 掉期计算如下：

   • 如果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

这篇关于使用堆的算法生成排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！