Re: Too many permutations computed

[tpeplt]

uzibalqa <uzibalqa@proton.me> writes:

> I have implemented the computations of permutations of a string using the 
> heap algorithm.
>

1. Here are the relevant lines of the algorithm* that you cited:

>         // 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

Note that in the ‘for’ statement, the condition is i < k-1.  This is due
to indexing starting at zero, i := 0, so indexing is from zero to length
- 1.  In your procedure, you have indexing ranging from zero to length:

>         (while (< j h)...

When this is changed to (while (< j (1- h))..., the procedure works
correctly.

*Heap’s Algorithm is named after B.R. Heap, rather than for ‘heap’ or
‘the heap’.

Here are some additional notes, but it should be possible to ignore them
and simply make the change above to get your procedure to work.

2. Your procedure contains the following expression that does not appear
to do anything so it might as well be deleted.

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

Here is the complete listing of your procedure with the changes listed,
above:

(defun permute-strg-heap (strg h result)
  "Collect permutations of string STRG of length H into list RESULT.
Use Heap’s Algorithm for computing all permutations."
  (if (= h 1)
      (progn
        (push (copy-sequence strg) result) ; Output the permutation
        (message "%s" strg))
    
    (progn
      (setq result
            (permute-strg-heap strg (1- h) result))
      (let ((j 0))
        (while (< j (1- h))
          ;; Generate permutations for i-th swapped with each i-1 initial
          ;; 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 strg (1- h) result))
          (setq j (1+ j))))))
  result)

3. No definition of the procedure ‘swap-chars’ was included in your
post.  Here is a simple (destructive) one that works with your
procedure:

(defun swap-chars (str p q)
  "Swap characters at indices P and Q in string STR.
This is destructive, that is, the value of STR is changed/lost."
  (let ((tmp (elt str p)))
    (aset str p (elt str q))
    (aset str q tmp)))

(setq my-string "abc")
my-string
=> "abc"

(swap-chars my-string 0 2)
my-string
=> "cba"

4. A wrapper procedure could be added for safety and convenience.

(defun permute (strg)
  "Generate a list of all permutations of the characters in string STRG."
  (if (string-empty-p strg)
      (list strg)
    (permute-strg-heap strg (length strg) '())))

(permute "")
=> ("")
(permute "a")
=> ("a")
(permute "ab")
=> ("ba" "ab")
(permute "abc")
=> ("cba" "bca" "acb" "cab" "bac" "abc")

This procedure will protect against empty strings that could lead to a
run-time error.  And it eliminates the need for the user to compute (or
make a mistake) the string’s length or to enter the constant '().

--