Too many permutations computed

Too many permutations computed

[uzibalqa]

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

But I am getting repetitions, which should not happen.  There could be some problems in the 
way  the recursive calls are handled, and the result list is not being updated correctly.

(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)  ; Output the permutation
        (message "%s" strg))

    (progn

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

      ;; Generate permutations for i-th swapped with each i-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 strg (1- h) result))

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

  result)


This should be tho algorithm


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

Re: Too many permutations computed

[Emanuel Berg]

uzibalqa wrote:

>         (while (< j h) [...]
>           (setq j (1+ j)))
>         [...]
>         for i := 0; i < k-1; i += 1 do [...]

You can replace that `while' with a for loop using `cl-loop'
and for, to make it a closer match to the pseudo-code.

This: (setq j (1+ j)) can be replaced by `cl-incf' as in
(cl-incf j) - but better yet is to get away with that and use
a for loop to iterate instead.

Again you can check out these two

  https://dataswamp.org/~incal/emacs-init/perm.el
  https://www.emacswiki.org/emacs/StringPermutations

but after spending so much time on your own solution I get it
you want to complete it ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: Too many permutations computed

[uzibalqa]

------- Original Message -------
On Wednesday, August 2nd, 2023 at 10:13 PM, Emanuel Berg <incal@dataswamp.org> wrote:

> uzibalqa wrote:
> 
> > (while (< j h) [...]
> > (setq j (1+ j)))
> > [...]
> > for i := 0; i < k-1; i += 1 do [...]
> 
> 
> You can replace that `while' with a for loop using` cl-loop'
> and for, to make it a closer match to the pseudo-code.
> 
> This: (setq j (1+ j)) can be replaced by `cl-incf' as in
> (cl-incf j) - but better yet is to get away with that and use
> a for loop to iterate instead.
> 
> Again you can check out these two
> 
> https://dataswamp.org/~incal/emacs-init/perm.el
> https://www.emacswiki.org/emacs/StringPermutations
> 
> but after spending so much time on your own solution I get it
> you want to complete it ...

Obviously, my implementation is not computing things as expected.
My current focus is to get it to work by being as close as possible 
to the algorithm so I can get it working as it should.
 
> --
> underground experts united
> https://dataswamp.org/~incal

Re: Too many permutations computed

[uzibalqa]

Sent with Proton Mail secure email.

------- Original Message -------
On Friday, August 4th, 2023 at 3:42 AM, uzibalqa <uzibalqa@proton.me> wrote:


> ------- Original Message -------
> On Wednesday, August 2nd, 2023 at 10:13 PM, Emanuel Berg incal@dataswamp.org wrote:
> 
> > uzibalqa wrote:
> > 
> > > (while (< j h) [...]
> > > (setq j (1+ j)))
> > > [...]
> > > for i := 0; i < k-1; i += 1 do [...]
> > 
> > You can replace that `while' with a for loop using` cl-loop'
> > and for, to make it a closer match to the pseudo-code.
> > 
> > This: (setq j (1+ j)) can be replaced by `cl-incf' as in
> > (cl-incf j) - but better yet is to get away with that and use
> > a for loop to iterate instead.

After doing 

     (cl-loop for j from 0 below (- h 1) do

I get the correct results.
 
> > Again you can check out these two
> > 
> > https://dataswamp.org/~incal/emacs-init/perm.el
> > https://www.emacswiki.org/emacs/StringPermutations
> > 
> > but after spending so much time on your own solution I get it
> > you want to complete it ...

There are many algorithms out there.  You should mention the kind
of algorithm you are implementing.  

I am using the original algorithm bf Robert Heap (1964).  It is not  
the common implementation you see because what I have seen is the
implementation of a simpler algorithm (programatically), but which
is not optimal in the way Robert constructed it.  
 
> Obviously, my implementation is not computing things as expected.
> My current focus is to get it to work by being as close as possible
> to the algorithm so I can get it working as it should.
> 
> > --
> > underground experts united
> > https://dataswamp.org/~incal

Re: Too many permutations computed

[Emanuel Berg]

uzibalqa wrote:

>> Again you can check out these two
>> 
>> https://dataswamp.org/~incal/emacs-init/perm.el
>> https://www.emacswiki.org/emacs/StringPermutations
>> 
>> but after spending so much time on your own solution I get it
>> you want to complete it ...
>
> There are many algorithms out there. You should mention the
> kind of algorithm you are implementing.

Not sure it has one? But it is for permutation of list
elements in general, the rest is just using it for the string
use case. Maybe Emacs should have a built-in permutation
function BTW, and a ditto library with helpers, e.g.
for strings ...

> I am using the original algorithm bf Robert Heap (1964).
> It is not the common implementation you see because what
> I have seen is the implementation of a simpler algorithm
> (programatically), but which is not optimal in the way
> Robert constructed it.

Okay, well, see if you can get it to work then ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: Too many permutations computed

[Heime]

------- Original Message -------
On Friday, August 4th, 2023 at 10:13 AM, Emanuel Berg <incal@dataswamp.org> wrote:


> uzibalqa wrote:
> 
> > > Again you can check out these two
> > > 
> > > https://dataswamp.org/~incal/emacs-init/perm.el
> > > https://www.emacswiki.org/emacs/StringPermutations
> > > 
> > > but after spending so much time on your own solution I get it
> > > you want to complete it ...
> > 
> > There are many algorithms out there. You should mention the
> > kind of algorithm you are implementing.
> 
> 
> Not sure it has one? But it is for permutation of list
> elements in general, the rest is just using it for the string
> use case. 

It does use a published technique, but did not take time to determine 
which one is it.  If I can space some time, I can check things out. 

> Maybe Emacs should have a built-in permutation
> function BTW, and a ditto library with helpers, e.g.
> for strings ...

That would make sense because permutations is quite a standard thing
today with a number of algorithms.  The implementation to use depends
on how much complication you are willing to accept programatically.
The more complicated, the more benefits you get.
 
> > I am using the original algorithm bf Robert Heap (1964).
> > It is not the common implementation you see because what
> > I have seen is the implementation of a simpler algorithm
> > (programatically), but which is not optimal in the way
> > Robert constructed it.
> 
> 
> Okay, well, see if you can get it to work then ...
> 
> --
> underground experts united
> https://dataswamp.org/~incal

Re: Too many permutations computed

[uzibalqa]

------- Original Message -------
On Wednesday, August 2nd, 2023 at 10:13 PM, Emanuel Berg <incal@dataswamp.org> wrote:


> uzibalqa wrote:
> 
> > (while (< j h) [...]
> > (setq j (1+ j)))
> > [...]
> > for i := 0; i < k-1; i += 1 do [...]

Do you understand what the i += 1 does ?  It is the same as i++,
am I right ?

The difference lies in the timing of when the increment takes place 
(immediately in the case of i += 1, and after the value is used in 
the case of i++).   Do you think the distinction mentioned makes a 
difference for the algorithm ?

> 
> You can replace that `while' with a for loop using` cl-loop'
> and for, to make it a closer match to the pseudo-code.
> 
> This: (setq j (1+ j)) can be replaced by `cl-incf' as in
> (cl-incf j) - but better yet is to get away with that and use
> a for loop to iterate instead.
> 
> Again you can check out these two
> 
> https://dataswamp.org/~incal/emacs-init/perm.el
> https://www.emacswiki.org/emacs/StringPermutations
> 
> but after spending so much time on your own solution I get it
> you want to complete it ...
> 
> --
> underground experts united
> https://dataswamp.org/~incal

Re: Too many permutations computed

[Emanuel Berg]

uzibalqa wrote:

>> (while (< j h) [...]
>> (setq j (1+ j)))
>> [...]
>> for i := 0; i < k-1; i += 1 do [...]
>
> Do you understand what the i += 1 does ? It is the same as
> i++, am I right ? The difference lies in the timing of when
> the increment takes place (immediately in the case of i +=
> 1, and after the value is used in the case of i++). Do you
> think the distinction mentioned makes a difference for the
> algorithm ?

It is up to the designer of the pseudo code to decide if it
works like that, if it does then it would make
a difference, yes.

See if you can write the Elisp as close as possible to the
pseudo code, including the variable names:

  (cl-loop for i from 0 to ... )

-- 
underground experts united
https://dataswamp.org/~incal

Re: Too many permutations computed

[Heime]

Sent with Proton Mail secure email.

------- Original Message -------
On Friday, August 4th, 2023 at 4:08 AM, Emanuel Berg <incal@dataswamp.org> wrote:


> uzibalqa wrote:
> 
> > > (while (< j h) [...]
> > > (setq j (1+ j)))
> > > [...]
> > > for i := 0; i < k-1; i += 1 do [...]
> > 
> > Do you understand what the i += 1 does ? It is the same as
> > i++, am I right ? The difference lies in the timing of when
> > the increment takes place (immediately in the case of i +=
> > 1, and after the value is used in the case of i++). Do you
> > think the distinction mentioned makes a difference for the
> > algorithm ?
> 
> 
> It is up to the designer of the pseudo code to decide if it
> works like that, if it does then it would make
> a difference, yes.
> 
> See if you can write the Elisp as close as possible to the
> pseudo code, including the variable names:
> 
> (cl-loop for i from 0 to ... )
 
Yes, I have got working properly with the cl-loop change.

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

--

Re: Too many permutations computed

[Emanuel Berg]

tpeplt wrote:

> (if (evenp h) [...]

Maybe that is a local function?

But if you replace that with

  (zerop (/ h 2))

it works as you say.

-- 
underground experts united
https://dataswamp.org/~incal

Re: Too many permutations computed

[tpeplt]

Emanuel Berg <incal@dataswamp.org> writes:

> tpeplt wrote:
>
>> (if (evenp h) [...]
>
> Maybe that is a local function?
>
> But if you replace that with
>
>   (zerop (/ h 2))
>
> it works as you say.

‘evenp’ is a local function?

C-h f evenp =>

evenp is an alias for ‘cl-evenp’ in ‘cl.el’.

(evenp INTEGER)

Return t if INTEGER is even.

  This function is obsolete since 27.1;
  use ‘cl-evenp’ instead.
  This function does not change global state, including the match data.

--

Re: Too many permutations computed

[Emanuel Berg]

tpeplt wrote:

>> Maybe that is a local function?
>>
>> But if you replace that with
>>
>>   (zerop (/ h 2))
>>
>> it works as you say.
>
> ‘evenp’ is a local function?
>
> C-h f evenp =>
>
> evenp is an alias for ‘cl-evenp’ in ‘cl.el’.

Aha, replace with

(require 'cl-lib)

and then `cl-evenp' as you say.

-- 
underground experts united
https://dataswamp.org/~incal