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

Please take the time to take the Tour and read the Help pages, especially What topics can I ask about here? and What types of questions should I avoid asking? — Tetsujin
– Tetsujin, Commented Aug 1, 2023 at 17:53
Was instructed it is the right place. What would be right place for algorithms? — Dilna
– Dilna, Commented Aug 1, 2023 at 17:57
Does this answer your question? Generating permutations with heap algorithm — Mokubai
– Mokubai, Commented Aug 3, 2023 at 10:09

rajashekar · Accepted Answer · 2024-01-28 21:30:35Z

2

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

edited Jan 28, 2024 at 21:30

answered Jan 28, 2024 at 21:17

rajashekar

3,82314 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Computing permutations with the Heap Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related