• Cprod (Cartesian Product) in Lisp (or Scheme)

    From HenHanna@21:1/5 to All on Tue May 21 12:18:52 2024
    XPost: comp.lang.scheme

    How would you write this in Lisp (or Scheme) ?



    in Python... (writing this out: itertools.product([0, 1], repeat=N )

    The value can be a list or a Tuple.

    cprod([0, 1], 1) => ((0) (1))

    cprod([0, 1], 2) => ((0,0) (0,1) (1,0) (1,1))


    This works:

    def cprod(x, c):
    if c==1: return [[i] for i in x]
    Sub= cprod(x, c-1)
    return [i for F in x for i in [[F]+R for R in Sub]]


    ---------- Is there another (better) way to write [F]+R ???

    it seems odd, compared to CONS in Lisp

    Other ways to improve it?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From HenHanna@21:1/5 to Spiros Bousbouras on Thu May 23 10:27:04 2024
    On 5/23/2024 8:46 AM, Spiros Bousbouras wrote:
    On Tue, 21 May 2024 12:18:52 -0700
    HenHanna <HenHanna@devnull.tb> wrote:


    How would you write this in Lisp (or Scheme) ?



    in Python... (writing this out: itertools.product([0, 1], repeat=N )

    The value can be a list or a Tuple.

    cprod([0, 1], 1) => ((0) (1))

    cprod([0, 1], 2) => ((0,0) (0,1) (1,0) (1,1))

    This is cartesian power rather than arbitrary cartesian product. Here
    is a Common Lisp version. It only works for vectors.

    (defun cartesian-power
    (vector power
    &aux (len (length vector)) (wheels (make-array power :initial-element 0))
    result (posres 0)
    )
    (when (or (eql power 0) (eql len 0))
    (return-from cartesian-power (make-array 0)))
    (setq result (make-array (expt len power)))
    (do () (nil)
    (setf (aref result posres)
    (map 'vector (lambda (a) (aref vector a)) wheels))
    (incf posres)
    (let ((pos (position-if (lambda (a) (< a (1- len))) wheels)))
    (unless pos (return-from cartesian-power result))
    (incf (aref wheels pos))
    (dotimes (i pos) (setf (aref wheels i) 0)))))

    Thanks!

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kaz Kylheku@21:1/5 to HenHanna on Fri May 24 02:00:11 2024
    XPost: comp.lang.scheme

    On 2024-05-21, HenHanna <HenHanna@devnull.tb> wrote:


    How would you write this in Lisp (or Scheme) ?



    in Python... (writing this out: itertools.product([0, 1], repeat=N )

    The value can be a list or a Tuple.

    cprod([0, 1], 1) => ((0) (1))

    cprod([0, 1], 2) => ((0,0) (0,1) (1,0) (1,1))

    Another name for this is "repeating permutations": permutations
    of the (0 1) elements, such that repetitions are allowed.

    How I would write this is by having it built into the language.

    This is the TXR Lisp interactive listener of TXR 294.
    Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet.
    Everything you type here can and will be used against you in
    comp.lang.lisp.
    (rperm '(0 1) 2)
    ((0 0) (0 1) (1 0) (1 1))

    I would have it as a lazy list, so we can ask for the first 5
    items of an incredibly long instance of such a sequence.

    (take 5 (rperm #\A..#\Z 15))
    ((#\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A)
    (#\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\B)
    (#\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\C)
    (#\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\D)
    (#\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\E))
    (take 5 (rperm (join #\A..#\Z) 15))
    ("AAAAAAAAAAAAAAA" "AAAAAAAAAAAAAAB" "AAAAAAAAAAAAAAC" "AAAAAAAAAAAAAAD"
    "AAAAAAAAAAAAAAE")

    That reminds me; I should probably implement iterators which
    step over these sequences, to complement the lazy list implementation.

    The implementation of rperm starts here:

    https://www.kylheku.com/cgit/txr/tree/combi.c?h=txr-294#n264

    The heart of it is the rperm_gen_fun function, which updates
    a permutation vector to the next permutation.

    The state consists of a vector of lists, and a reset list.

    For instance, if we are generating triplets of (A B C D), the
    vector gets initialized to a copy of the list in every position:

    #((A B C D)
    (A B C D)
    (A B C D))

    We take the first repeating permutation by taking the car
    of every list: (A A A A). Then to generate the next permutation,
    we pop the last list:

    #((A B C D)
    (A B C D)
    (B C D)) ;; pop!

    When we pop the last list empty, we restore it back to (A B C D),
    and pop the next one:

    #((A B C D)
    (A B C D)
    (B))

    #((A B C D)
    (A B C D)
    ()) ;; pop! oops!

    #((A B C D)
    (B C D) ;; pop!
    (A B C D)) ;; whump! (restored)

    When we pop the first list down to nil, then we are done.
    The rperm_while_fun tests for this condition.

    It's a very simple algorithm compared to the nonrepeating
    permutations, and repeating or nonrepeating combinations.

    --
    TXR Programming Language: http://nongnu.org/txr
    Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
    Mastodon: @Kazinator@mstdn.ca

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)