使用堆算法计算排列

Question

我正在使用以下堆算法来计算 elisp 中单词的排列，但排列不正确。

问题可能与我使用两次

permute-strg-heap

调用的方式有关。 我很确定我必须调用

(copy-sequence strg)

而不是

strg

，这样就不会发生冲突。

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

这就是我想要复制的

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

Answer 1

(while (< j h) ...)

应该是

(while (< j (1- h)))

。

当你改变它时它就会起作用。调试递归函数时，使用

trace-function

有助于跟踪其调用。

(trace-function #'permute-strg-heap)

版本错误，带有

(while (< j h))

1 -> (permute-strg-heap "ab" 2)
| 2 -> (permute-strg-heap "ab" 1 nil)
| 2 <- permute-strg-heap: ("ab")
| 2 -> (permute-strg-heap "ba" 1 ("ab"))
| 2 <- permute-strg-heap: ("ba" "ab")
| 2 -> (permute-strg-heap "ba" 1 ("ba" "ab"))
| 2 <- permute-strg-heap: ("ba" "ba" "ab")
1 <- permute-strg-heap: ("ba" "ba" "ab")

正确版本为

(while (< j (1- h)))

1 -> (permute-strg-heap "ab" 2)
| 2 -> (permute-strg-heap "ab" 1 nil)
| 2 <- permute-strg-heap: ("ab")
| 2 -> (permute-strg-heap "ba" 1 ("ab"))
| 2 <- permute-strg-heap: ("ba" "ab")
1 <- permute-strg-heap: ("ba" "ab")