使用堆算法生成排列

Question

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

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

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)

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

Answer 1

要在 R 中实现 Heap's algorithm，这里有一个解决方案，将结果输出到矩阵中以供进一步处理：

h <- function(s, n, e, ...) {
  ## processes Heap's algorithm
  if (n == 1L) {
    e$i <- e$i + 1L
    e$r[e$i, ] <- e$s
  } else {
    h(s, n - 1L, e)
    for (i in 1:(n - 1L)) {
      if (n %% 2L == 0L) {
        j <- i
      } else {
        j <- 1L
      }
      tmp <- e$s[n]
      e$s[n] <- e$s[j]
      e$s[j] <- tmp
      h(s, n - 1L, e)
    } 
  }
}

hperm <- function(s) {
  ## wrapper
  e <- environment()
  l <- length(s)
  i <- 0L
  e$r <- matrix(NA, factorial(l), l)
  h(s, l, e, i)
  return(e$r)
}

给出：

A <- 0:3

hperm(A)
#       [,1] [,2] [,3] [,4]
#  [1,]    0    1    2    3
#  [2,]    1    0    2    3
#  [3,]    2    0    1    3
#  [4,]    0    2    1    3
#  [5,]    1    2    0    3
#  [6,]    2    1    0    3
#  [7,]    3    1    0    2
#  [8,]    1    3    0    2
#  [9,]    0    3    1    2
# [10,]    3    0    1    2
# [11,]    1    0    3    2
# [12,]    0    1    3    2
# [13,]    0    2    3    1
# [14,]    2    0    3    1
# [15,]    3    0    2    1
# [16,]    0    3    2    1
# [17,]    2    3    0    1
# [18,]    3    2    0    1
# [19,]    3    2    1    0
# [20,]    2    3    1    0
# [21,]    1    3    2    0
# [22,]    3    1    2    0
# [23,]    2    1    3    0
# [24,]    1    2    3    0

另请参阅： of Heap's algorithm on Stack Overflow。

Answer 2

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

维基百科中 Heap 算法的实现假设 0-based 索引，而 R 的向量是 1-based .所以A[0]需要翻译成A[1]（也就是数组的第一个元素），而A[n-1]需要翻译成A[n]（也就是最后一个元素）在 n-A 的前缀中）。
令人惊讶的是，该代码不遵循维基百科代码的迭代结构。剥离其本质，正确的代码是（更改为基于 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算法满足的“格雷码”要求的本质。
各种伪代码实现（以及 Python 中的具体实现）假定数组参数实际上是通过引用传递的，因此递归调用中的交换对调用者可见。但是 R 通过 value 传递数组，因此每个递归调用都有自己的数组实例，并且修改不会反映在调用者的数组中。
掉期计算如下：
- 如果 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）；
每个生成的排列都是唯一的；
两个连续的排列仅在一次交换中不同。

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

这是上述 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

使用堆算法生成排列

Generate Permutations using Heap's Algorithm

r

algorithm

recursion

permutation

heaps-algorithm

给出：