基于Heap算法的排列计算：Elisp实现结果异常排查

问题背景 #

我用Elisp实现Heap算法生成字符串排列，但输出结果不正确。我怀疑问题出在两次调用permute-strg-heap的方式上，且确定必须通过(copy-sequence strg)而非直接传入strg来避免状态冲突。

原Elisp实现代码 #

(defun permute-strg-heap (strg h &optional result)
  "Generate all permutations of string STRG using recursive
backtracking."

  (if (null result) (setq result '()))

  (if (= h 1)

      (progn
        (push strg result)  ; Output the permutation
        (message "%s" strg))

    (setq result
      (permute-strg-heap (copy-sequence strg) (1- h) result))

    ;; Generate permutations for j-th swapped with each j-1 initial
    (let ( (j 0) )
      (while (< j h)

        ;; Swap choice based upon h (even or odd)
        (if (evenp h)
            (swap-chars strg j (1- h))
          (swap-chars strg 0 (1- h)))

        (setq result
          (permute-strg-heap (copy-sequence strg) (1- h) result))

        (setq j (1+ j)))))

  result)

目标复刻的标准Heap算法伪代码 #

procedure generate(k : integer, A : array of any):
    if k = 1 then
        output(A)
    else
        // Generate permutations with k-th unaltered
        // Initially k = length(A)
        generate(k - 1, A)

        // Generate permutations for k-th swapped with each k-1 initial
        for i := 0; i < k-1; i += 1 do
            // Swap choice dependent on parity of k (even or odd)
            if k is even then
                swap(A[i], A[k-1]) // zero-indexed, the k-th is at k-1
            else
                swap(A[0], A[k-1])
            end if
            generate(k - 1, A)
        end for
    end if

问题分析与修复 #

对比伪代码和Elisp实现，存在三个核心问题：

• 循环边界错误：伪代码中循环条件是i < k-1，但Elisp里写的是j < h，导致多执行了一次循环，破坏排列生成逻辑。应将循环条件改为j < (1- h)。
• 第一次递归的不必要拷贝：伪代码中第一次递归直接传入原数组A，而Elisp里传入了(copy-sequence strg)，这会导致后续交换操作基于拷贝后的字符串，违背Heap算法原地修改、回溯的核心逻辑。第一次递归应直接传strg。
• 结果存储时未拷贝字符串：当h=1时直接push strg result，后续交换操作会修改原字符串内容，导致结果列表中所有元素都是同一个字符串引用，最终结果全部变成最后一次修改后的样子。需要改为push (copy-sequence strg) result保存当前状态的副本。

修复后的Elisp代码 #

(defun permute-strg-heap (strg h &optional result)
  "Generate all permutations of string STRG using recursive backtracking."
  (if (null result)
      (setq result '()))

  (if (= h 1)
      (progn
        (push (copy-sequence strg) result)  ; 保存当前状态的副本
        (message "%s" strg))
    ;; 第一次递归直接传原字符串，不拷贝
    (setq result (permute-strg-heap strg (1- h) result))

    ;; 循环条件修正为 j < (1- h)
    (let ((j 0))
      (while (< j (1- h))
        (if (evenp h)
            (swap-chars strg j (1- h))
          (swap-chars strg 0 (1- h)))
        ;; 递归前拷贝当前字符串，避免后续修改影响已生成的结果
        (setq result (permute-strg-heap (copy-sequence strg) (1- h) result))
        (setq j (1+ j)))))

  result)

内容的提问来源于stack exchange，提问作者Dilna