List not getting filled up

List not getting filled up

[uzibalqa]

I have the recursive function 'permutor'.  When the condition '(<= k 1)' is reached I add
word to the list 'mylist'.  I only get one value, yet the '(message "%s" word)' give me all
the words that I need.  What is happening and what can I do ?

(defvar mylist '())

(defun permutor (k word)
  "Generate all permutations of WORD."

  (let ( (i 0) )

    (if (<= k 1)
        (progn
          (message "%s" word)
          (add-to-list 'mylist word))

      (while (< i k)
        (permutor (1- k) word)

        (if (evenp i)  ; even integer
            (setq word (swap word i (1- k)))

          (setq word (swap word 0 (1- k))))

        (setq i (1+ i)))) )

      word)

Re: List not getting filled up

[Emanuel Berg]

uzibalqa wrote:

> (add-to-list 'mylist word))

It is this line.

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

Re: List not getting filled up

[tpeplt]

uzibalqa <uzibalqa@proton.me> writes:

> I have the recursive function 'permutor'.  When the condition '(<= k 1)' is reached I add
> word to the list 'mylist'.  I only get one value, yet the '(message "%s" word)' give me all
> the words that I need.  What is happening and what can I do ?
>
> (defvar mylist '())
>
> (defun permutor (k word)
>   "Generate all permutations of WORD."
>
>   (let ( (i 0) )
>
>     (if (<= k 1)
>         (progn
>           (message "%s" word)
>           (add-to-list 'mylist word))
>
>       (while (< i k)
>         (permutor (1- k) word)
>
>         (if (evenp i)  ; even integer
>             (setq word (swap word i (1- k)))
>
>           (setq word (swap word 0 (1- k))))
>
>         (setq i (1+ i)))) )
>
>       word)

 1. Provide a specification of the problem that you want your
    procedure to solve.  For example, provide calls to your
    procedure with a range of values and the results that you want
    your procedure to produce:

    (permutor 0 'aword) should yield => what?
    (permutor 1 'aword) should yield => what?
    (permutor 5 'aword) should yield => what?
    (permutor 9 'aword) should yield => what?

 2. Compiling an Emacs Lisp file can provide useful information
    about possible problems with the code.  Once an Emacs Lisp
    buffer has been saved to a file (usually with the filename
    extension ".el"), it can be compiled using the "Byte-compile
    This File" menu entry in the Emacs-Lisp menu.  Alternatively,
    you can use the command M-x byte-compile-file.  When this is
    done on your code, the compiler tells you that the function
    ‘swap’ is not known to be defined.

 3. Emacs provides ‘edebug’, a debugger which allows you to step
    through your code, examining values of variables as you go so
    that you can compare what you expect to happen with what is
    happening.  To use edebug, you will need to "instrument" the
    procedure that you want to step through and then invoke the
    procedure with your desired arguments.  Again, the Emacs-Lisp
    menu provides a menu entry for you to do this, "Instrument
    Function for Debugging", and it documents that you can do this
    using the keystroke combination C-u C-M-x (when point is
    located in the procedure).  An introduction to edebug can be
    found in the Introduction to Emacs Lisp, which can be read via
    the menu path: Help -> More Manuals -> Introduction to Emacs
    Lisp.  Or, you can go directly to the debugging section with
    the command:

       M-: (info "(eintr) Debugging")

    The full documents on Emacs two debuggers can be read in the
    Emacs Lisp reference manual

       M-: (info "(elisp) Debugging")

--

Re: List not getting filled up

[uzibalqa]

------- Original Message -------
On Monday, July 31st, 2023 at 2:28 AM, tpeplt <tpeplt@gmail.com> wrote:

> uzibalqa uzibalqa@proton.me writes:

> 1. Provide a specification of the problem that you want your
> procedure to solve. For example, provide calls to your
> procedure with a range of values and the results that you want
> your procedure to produce:

Use this as a test

(setq collection '())
(permute "abc" 0 3 collection) 
(message "%s" collection)

I should get

collection (abc acb bac bca cba cab)

But I get

Collection (abc abc abc abc abc abc)

Here is the function permute

(defun permute (string i length &optional result)
  "Generate permutations of STRING using Backtracking Algorithm."

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

  (if (= i length)
      
      (progn (message "%s" string)
             (push string result))

    (let ( (j i) )
      (while (< j length)
        (swap-chars string i j)
        ;; Update result through recursion
        (setq result (permute string (1+ i) length result))
        (swap-chars string i j)
        (setq j (1+ j))) ))

  result)

Here is the supporting function swap-chars

(defun swap-chars (string p q)
  "Swap chars in STRING at positions P and Q.
This is a destructive operation."

  (aset string p                         ; Store char d at index p
    (prog1 (aref string q)               ; Save character d
      (aset string q (aref string p))))  ; Store char b at index q

  string)

Re: List not getting filled up

[Yuri Khan]

On Sun, 30 Jul 2023 at 22:11, uzibalqa <uzibalqa@proton.me> wrote:

> Use this as a test
>
> (setq collection '())
> (permute "abc" 0 3 collection)
> (message "%s" collection)
>
> I should get
>
> collection (abc acb bac bca cba cab)
>
> But I get
>
> Collection (abc abc abc abc abc abc)

You have a function that builds a list of strings.

Initially, you have an initial string value, "abc". Along the way, you
modify its contents, but ultimately there is only one string instance
in your program.

Each time you ‘push’ that string into your ‘result’ list, you are
storing one more reference to the same string object. In
box-and-pointer diagrams:

    ┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌───┬───┐
    │ * │ *─┼──→│ * │ *─┼──→│ * │ *─┼──→│ * │ *─┼──→│ * │ *─┼──→│ * │nil│
    └─┼─┴───┘   └─┼─┴───┘   └─┼─┴───┘   └─┼─┴───┘   └─┼─┴───┘   └─┼─┴───┘
      │┌──────────┘           │           │           │           │
      ││┌─────────────────────┘           │           │           │
      │││┌────────────────────────────────┘           │           │
      ││││┌───────────────────────────────────────────┘           │
      │││││┌──────────────────────────────────────────────────────┘
      ↓↓↓↓↓↓
      ┌──────────────────┐
      │ (mutable string) │
      └──────────────────┘

This explains why you get a list that looks like it contains 6
identical strings — they are *the same* string.

Instead, you should be avoiding in-place string mutation and building
new string instances as you go, perhaps by redefining ‘swap-chars’ to
be non-destructive:

    (defun swap-chars (string p q)
      "Swap chars in STRING at positions P and Q."
      (cond
       ((= p q) string)
       ((> p q) (swap-chars string q p))
       (t (concat
           (substring string 0 p)
           (substring string q (1+ q))
           (substring string (1+ p) q)
           (substring string p (1+ p))
           (substring string (1+ q))))))

(This is likely not the fastest way to build a string with two
characters swapped. Do not let that distract you from the goal. Your
first goal is to get your program working correctly. When and if that
happens, and when and if your working solution is deemed too slow,
only then you start optimizing.)

(Adjusting the ‘permute’ function to non-destructive behavior of
‘swap-chars’ is left as an exercise. Hint 1: in your first
‘swap-chars’ call, you need to arrange for the return value to be
passed to the recursive invocation of ‘permute’. Hint 2: your second
‘swap-chars’ call is only there to undo the modification made by the
first call, so it could be avoided by introducing a local variable to
hold the result of the modification.)

Re: List not getting filled up

[uzibalqa]

------- Original Message -------
On Monday, July 31st, 2023 at 5:42 AM, Yuri Khan <yuri.v.khan@gmail.com> wrote:


> On Sun, 30 Jul 2023 at 22:11, uzibalqa uzibalqa@proton.me wrote:
> 
> > Use this as a test
> > 
> > (setq collection '())
> > (permute "abc" 0 3 collection)
> > (message "%s" collection)
> > 
> > I should get
> > 
> > collection (abc acb bac bca cba cab)
> > 
> > But I get
> > 
> > Collection (abc abc abc abc abc abc)
> 
> 
> You have a function that builds a list of strings.
> 
> Initially, you have an initial string value, "abc". Along the way, you
> modify its contents, but ultimately there is only one string instance
> in your program.
> 
> Each time you ‘push’ that string into your ‘result’ list, you are
> storing one more reference to the same string object. In
> box-and-pointer diagrams:
> 
> ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐
> │ * │ *─┼──→│ * │ *─┼──→│ * │ *─┼──→│ * │ *─┼──→│ * │ *─┼──→│ * │nil│
> └─┼─┴───┘ └─┼─┴───┘ └─┼─┴───┘ └─┼─┴───┘ └─┼─┴───┘ └─┼─┴───┘
> │┌──────────┘ │ │ │ │
> ││┌─────────────────────┘ │ │ │
> │││┌────────────────────────────────┘ │ │
> ││││┌───────────────────────────────────────────┘ │
> │││││┌──────────────────────────────────────────────────────┘
> ↓↓↓↓↓↓
> ┌──────────────────┐
> │ (mutable string) │
> └──────────────────┘
> 
> This explains why you get a list that looks like it contains 6
> identical strings — they are the same string.
> 
> Instead, you should be avoiding in-place string mutation and building
> new string instances as you go, perhaps by redefining ‘swap-chars’ to
> be non-destructive:
> 
> (defun swap-chars (string p q)
> "Swap chars in STRING at positions P and Q."
> (cond
> ((= p q) string)
> ((> p q) (swap-chars string q p))
> 
> (t (concat
> (substring string 0 p)
> (substring string q (1+ q))
> (substring string (1+ p) q)
> (substring string p (1+ p))
> (substring string (1+ q))))))
> 
> (This is likely not the fastest way to build a string with two
> characters swapped. Do not let that distract you from the goal. Your
> first goal is to get your program working correctly. When and if that
> happens, and when and if your working solution is deemed too slow,
> only then you start optimizing.)
> 
> (Adjusting the ‘permute’ function to non-destructive behavior of
> ‘swap-chars’ is left as an exercise. Hint 1: in your first
> ‘swap-chars’ call, you need to arrange for the return value to be
> passed to the recursive invocation of ‘permute’. 

Have done a non-destructive swap-chars which I use directly as follows

(setq result
          (permute (swap-chars string i j) (1+ i) length result))

>  Hint 2: your second
> ‘swap-chars’ call is only there to undo the modification made by the
> first call, so it could be avoided by introducing a local variable to
> hold the result of the modification.)

For your second hint, I am unsure what to store.  Would I store the original 
string passed as an argument to the function as follows.  Then what would I 
do with copy of the string that war not swapped ?


    (let ( (j i)
           (str string) )

      (while (< j length)
        (setq result
          (permute (swap-chars string i j) (1+ i) length result))
        (setq j (1+ j))) ))

RE: [External] : Re: List not getting filled up

[Drew Adams]

> Each time you ‘push’ that string into your ‘result’ list, you are
> storing one more reference to the same string object. 
> 
> This explains why you get a list that looks like it contains 6
> identical strings — they are *the same* string.
> 
> Instead, you should be avoiding in-place string mutation and building
> new string instances as you go, perhaps by redefining ‘swap-chars’ to
> be non-destructive:
> 
>     (defun swap-chars (string p q)
>       "Swap chars in STRING at positions P and Q."
>       (cond
>        ((= p q) string)
>        ((> p q) (swap-chars string q p))
>        (t (concat
>            (substring string 0 p)
>            (substring string q (1+ q))
>            (substring string (1+ p) q)
>            (substring string p (1+ p))
>            (substring string (1+ q))))))
> 
> (This is likely not the fastest way to build a string with two
> characters swapped. Do not let that distract you from the goal. Your
> first goal is to get your program working correctly. When and if that
> happens, and when and if your working solution is deemed too slow,
> only then you start optimizing.)
> 
> (Adjusting the ‘permute’ function to non-destructive behavior of
> ‘swap-chars’ is left as an exercise. Hint 1: in your first
> ‘swap-chars’ call, you need to arrange for the return value to be
> passed to the recursive invocation of ‘permute’. Hint 2: your second
> ‘swap-chars’ call is only there to undo the modification made by the
> first call, so it could be avoided by introducing a local variable to
> hold the result of the modification.)

Another possibility is to go ahead and change
the string "destructively", over and over, but
create a new string from the result after each
modification, and add that new string to the
list.  You can do that with `copy-seq', `format',
or `concat'.

What's important to understand is what Yuri
explained, including the fact that how you get
get separate strings to add to the list is less
important than understanding that you need to
do that.  I'm only pointing out that you need
not forego the use of destructive modification
just because you need to end up with multiple,
separate strings.

RE: [External] : Re: List not getting filled up

[uzibalqa]

Sent with Proton Mail secure email.

------- Original Message -------
On Monday, July 31st, 2023 at 12:50 PM, Drew Adams <drew.adams@oracle.com> wrote:


> > Each time you ‘push’ that string into your ‘result’ list, you are
> > storing one more reference to the same string object.
> > 
> > This explains why you get a list that looks like it contains 6
> > identical strings — they are the same string.
> > 
> > Instead, you should be avoiding in-place string mutation and building
> > new string instances as you go, perhaps by redefining ‘swap-chars’ to
> > be non-destructive:
> > 
> > (defun swap-chars (string p q)
> > "Swap chars in STRING at positions P and Q."
> > (cond
> > ((= p q) string)
> > ((> p q) (swap-chars string q p))
> > (t (concat
> > (substring string 0 p)
> > (substring string q (1+ q))
> > (substring string (1+ p) q)
> > (substring string p (1+ p))
> > (substring string (1+ q))))))
> > 
> > (This is likely not the fastest way to build a string with two
> > characters swapped. Do not let that distract you from the goal. Your
> > first goal is to get your program working correctly. When and if that
> > happens, and when and if your working solution is deemed too slow,
> > only then you start optimizing.)
> > 
> > (Adjusting the ‘permute’ function to non-destructive behavior of
> > ‘swap-chars’ is left as an exercise. Hint 1: in your first
> > ‘swap-chars’ call, you need to arrange for the return value to be
> > passed to the recursive invocation of ‘permute’. Hint 2: your second
> > ‘swap-chars’ call is only there to undo the modification made by the
> > first call, so it could be avoided by introducing a local variable to
> > hold the result of the modification.)
> 
> 
> Another possibility is to go ahead and change
> the string "destructively", over and over, but
> create a new string from the result after each
> modification, and add that new string to the
> list. You can do that with `copy-seq',` format',
> or `concat'.
> 
> What's important to understand is what Yuri
> explained, including the fact that how you get
> get separate strings to add to the list is less
> important than understanding that you need to
> do that. I'm only pointing out that you need
> not forego the use of destructive modification
> just because you need to end up with multiple,
> separate strings.

Have also tried to go through the non-destructive route with this,
but the results are not the same.  Any idea what might I be doing 
wrong ?   Have removed the first swap-chars and pass it directly to
the internal permute.  Then I would not need to call swap-chars a 
second time.

This task is quite hard.

(defun permute (string i length &optional result)
  "Generate permutations of STRING using Backtracking Algorithm."

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

  (if (= i length)

      (progn (message "Output %s" string)
             (push (copy-sequence string) result))

    (let ( (j i) )
      (while (< j length)
        (setq result
          (permute (swap-chars string i j) (1+ i) length result))
        (setq j (1+ j))) ))

  result)

RE: [External] : Re: List not getting filled up

[Drew Adams]

> > Another possibility is to go ahead and change
> > the string "destructively", over and over, but
> > create a new string from the result after each
> > modification, and add that new string to the
> > list. You can do that with `copy-seq',` format',
> > or `concat'.
> 
> Have also tried to go through the non-destructive route with this,
> but the results are not the same.  Any idea what might I be doing
> wrong ?   Have removed the first swap-chars and pass it directly to
> the internal permute.  Then I would not need to call swap-chars a
> second time.

I'm not looking at your code.  I'm saying that
if you can destructively modify the same string
multiple times, and if you want a copy of each
such result to be added to a list as a separate
(i.e., new) string, you can just copy the string
you modified and add that copy to your list.

I said you can copy the string value of var `foo'
using (copy-sequence foo) or (concat foo nil) or
(format "%S" foo).

I was wrong about the last one.

(eq foo (copy-sequence foo)) ; -> nil
(eq foo (concat foo nil))    ; -> nil
(eq foo (format "%s" foo))   ; -> t

RE: [External] : Re: List not getting filled up

[uzibalqa]

------- Original Message -------
On Monday, July 31st, 2023 at 1:29 PM, Drew Adams <drew.adams@oracle.com> wrote:


> > > Another possibility is to go ahead and change
> > > the string "destructively", over and over, but
> > > create a new string from the result after each
> > > modification, and add that new string to the
> > > list. You can do that with `copy-seq',` format',
> > > or `concat'.
> > 
> > Have also tried to go through the non-destructive route with this,
> > but the results are not the same. Any idea what might I be doing
> > wrong ? Have removed the first swap-chars and pass it directly to
> > the internal permute. Then I would not need to call swap-chars a
> > second time.
> 
> 
> I'm not looking at your code. I'm saying that
> if you can destructively modify the same string
> multiple times, and if you want a copy of each
> such result to be added to a list as a separate
> (i.e., new) string, you can just copy the string
> you modified and add that copy to your list.
> 
> I said you can copy the string value of var `foo'
> using (copy-sequence foo) or (concat foo nil) or
> (format "%S" foo).
> 
> I was wrong about the last one.
> 
> (eq foo (copy-sequence foo)) ; -> nil
> 
> (eq foo (concat foo nil)) ; -> nil
> 
> (eq foo (format "%s" foo)) ; -> t

Upon further introspection I found that it makes a lot of difference
whether I use

(push (copy-sequence string) result)

or

(push string result)

Why is that ?

RE: [External] : Re: List not getting filled up

[Drew Adams]

> Upon further introspection I found that it makes a lot of difference
> whether I use
> 
> (push (copy-sequence string) result)
> or
> (push string result)
> 
> Why is that ?

Because of just what everyone's been saying:

If you add the string to the list then you
add the same string each time, because the
variable `string' refers to the same Lisp
object (same string), as shown by `eq'.

If you add a copy of the string the copy
reflects the current state of the string.

As I wrote:
(eq foo (copy-sequence foo)) ; -> nil

RE: [External] : Re: List not getting filled up

[uzibalqa]

------- Original Message -------
On Monday, July 31st, 2023 at 1:40 PM, Drew Adams <drew.adams@oracle.com> wrote:


> > Upon further introspection I found that it makes a lot of difference
> > whether I use
> > 
> > (push (copy-sequence string) result)
> > or
> > (push string result)
> > 
> > Why is that ?
> 
> Because of just what everyone's been saying:
> 
> If you add the string to the list then you
> add the same string each time, because the
> variable `string' refers to the same Lisp object (same string), as shown by` eq'.

This is certainly defeating me.
 
> If you add a copy of the string the copy
> reflects the current state of the string.

string is being passed as argument to function permute, how does it not reflect
its current state ?
 
> As I wrote:
> (eq foo (copy-sequence foo)) ; -> nil
 
Could I have a real example of how they would be different ? 

RE: [External] : Re: List not getting filled up

[Heime]

------- Original Message -------
On Monday, July 31st, 2023 at 2:03 PM, uzibalqa <uzibalqa@proton.me> wrote:


> ------- Original Message -------
> On Monday, July 31st, 2023 at 1:40 PM, Drew Adams drew.adams@oracle.com wrote:
> 
> 
> 
> > > Upon further introspection I found that it makes a lot of difference
> > > whether I use
> > > 
> > > (push (copy-sequence string) result)
> > > or
> > > (push string result)
> > > 
> > > Why is that ?
> > 
> > Because of just what everyone's been saying:
> > 
> > If you add the string to the list then you
> > add the same string each time, because the
> > variable `string' refers to the same Lisp object (same string), as shown by` eq'.
> 
> 
> This is certainly defeating me.
> 
> > If you add a copy of the string the copy
> > reflects the current state of the string.
> 
> 
> string is being passed as argument to function permute, how does it not reflect
> its current state ?
> 
> > As I wrote:
> > (eq foo (copy-sequence foo)) ; -> nil
> 
> 
> Could I have a real example of how they would be different ?

I have just done

      (progn
        (let* ( (cseq (copy-sequence strg)) )
          (message "Output %s %s" strg cseq)
          (push (copy-sequence strg) result)))

And the result is always that strg and cseq constitute the same characters.
At no time are they different.  So how is pushing one or the other push
something different ? 

Re: List not getting filled up

[Yuri Khan]

On Mon, 31 Jul 2023 at 07:06, uzibalqa <uzibalqa@proton.me> wrote:

> Have done a non-destructive swap-chars which I use directly as follows
>
> (setq result
>           (permute (swap-chars string i j) (1+ i) length result))
>
> >  Hint 2: your second
> > ‘swap-chars’ call is only there to undo the modification made by the
> > first call, so it could be avoided by introducing a local variable to
> > hold the result of the modification.)
>
> For your second hint, I am unsure what to store.  Would I store the original
> string passed as an argument to the function as follows.  Then what would I
> do with copy of the string that war not swapped ?

If you pass the return value of ‘swap-chars’ directly into ‘permute’,
nothing additional is needed. You could alternatively use

    (let ((swapped (swap-chars string i j)))
      (setq result (permute swapped (1+ i) length result)))

in case you find that easier to read.