Computing permutations with the Heap Algorithm

Question

I am using the following the Heap Algorithm for computing permutation of words in elisp, but the permutations are not correct.

The problem could be associated with the way I use the two calls to permute-strg-heap. I am quite sure that I have to call (copy-sequence strg) rather than strg so there will be no conflicts.

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

This is what I am trying to replicate

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) ...) should be (while (< j (1- h)) ...).

It works when you change that. When debugging recursive functions, it helps to trace their invocations with trace-function.

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

Wrong version with (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")

Correct version with (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")