2

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

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

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)

输出没有显示，如果能得到一些帮助会很棒。

4

2 回答 2

4

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

  1. Wikipedia 中 Heap 算法的实现假设基于 0 的索引，而 R 的向量是基于 1 的。soA[0]需要翻译成A[1]（即数组中的第一个元素），whileA[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交换。结果是两个连续排列之间恰好有一次交换，这是堆算法满足的“格雷码”要求的本质。

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

  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))
}

在测试堆算法的实现时，使用至少包含 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
于 2022-01-01T21:16:40.937 回答
0

为了在 R 中实现Heap 算法，这里有一个解决方案，将结果输出到矩阵中以供进一步处理：

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

另请参阅： 堆栈溢出上堆算法的Python 代码。

于 2022-01-01T10:03:30.667 回答