1. Forum
  2. Usenet
  3. COMP.LANG.LISP

  • Rather simple list/set operation [?]

    From B. Pym@21:1/5 to Drew Krause on Fri Jun 7 07:56:53 2024
    From: Drew Krause
    Subject: rather simple list/set operation
    Date: Tue, 3 Jan 2012 19:01:19 -0600


    Drew Krause wrote:

    Maybe someone can help me with this?

    I start with a list, e.g.

    ((0) (1 3) (1 2) (4 6) (5 7) (7 8))


    and want all members of intersecting lists to appear in the same sublist:

    ((0) (1 2 3) (4 6) (5 7 8))

    Gauche Scheme:

    (use srfi-1) ; "lset-" functions
    (use srfi-42) ; do-ec

    (define (coalesce lists)
    (define accum '())
    (do-ec (:list x lists)
    (receive
    (miss hit)
    (partition (lambda (y) (null? (lset-intersection equal? x y)))
    accum)
    (set! accum
    (cons (apply lset-union equal? x hit) miss))))
    accum)


    (coalesce '((2 4) (8 9) (4 5 8)))
    ===>
    ((2 9 4 5 8))

    (coalesce '((2 4) (3 9) (5 6) (2 3)))

    ((4 9 2 3) (5 6))

    (coalesce '((0) (1 3) (1 2) (4 6) (5 7) (7 8)))

    ((5 7 8) (4 6) (3 1 2) (0))

    (coalesce '((2 4) (3 9) (5 6) (2 3) (55 66) (0) (66 6)))

    ((5 55 66 6) (0) (4 9 2 3))

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Jeff Barnett@21:1/5 to B. Pym on Fri Jun 7 12:07:33 2024
    On 6/7/2024 1:56 AM, B. Pym wrote:

    From: Drew Krause
    Subject: rather simple list/set operation
    Date: Tue, 3 Jan 2012 19:01:19 -0600


    Drew Krause wrote:

    Maybe someone can help me with this?

    I start with a list, e.g.

    ((0) (1 3) (1 2) (4 6) (5 7) (7 8))


    and want all members of intersecting lists to appear in the same sublist:

    ((0) (1 2 3) (4 6) (5 7 8))
    I think the problem definition is ambiguous and not clarified by the
    example. Consider the following input lists:
    ((0 1) (1 2) (2 3)),
    ((0 1) (0 2) (0 3)).
    Any idea what Krause had in mind?
    --
    Jeff Barnett

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Jeff Barnett@21:1/5 to Jens Kallup on Fri Jun 7 12:38:40 2024
    On 6/7/2024 12:31 PM, Jens Kallup wrote:
    Am 2024-06-07 um 20:07 schrieb Jeff Barnett:
    Any idea what Krause had in mind?
    linked lists

    I'd love to see and Krause jointly specify a problem.
    --
    Jeff Barnett

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Madhu@21:1/5 to All on Sat Jun 8 21:35:34 2024
    * Jeff Barnett <v3vi98$25sr1$1@dont-email.me> :
    Wrote on Fri, 7 Jun 2024 12:07:33 -0600:

    On 6/7/2024 1:56 AM, W J wrote:
    From: Drew Krause
    Subject: rather simple list/set operation
    Date: Tue, 3 Jan 2012 19:01:19 -0600
    Drew Krause wrote:
    Maybe someone can help me with this?
    I start with a list, e.g.

    ((0) (1 3) (1 2) (4 6) (5 7) (7 8))


    and want all members of intersecting lists to appear in the same sublist: >>>
    ((0) (1 2 3) (4 6) (5 7 8))

    I think the problem definition is ambiguous and not clarified by the
    example.
    Consider the following input lists:
    ((0 1) (1 2) (2 3)),
    ((0 1) (0 2) (0 3)).
    Any idea what Krause had in mind?


    One way to answer this is to write a program and define the problem to
    by what the program solves.

    Here is a suitably cringeworthy function to do that in lisp.

    (defun krause-group (list-of-lists &aux ret)
    (dolist (list list-of-lists)
    (assert (consp list))
    (let ((cons (or (find-if (lambda (x) (find (car list) x)) ret)
    (let ((cons (list (car list))))
    (push cons ret)
    cons))))
    (dolist (elt (cdr list))
    (unless (find elt cons)
    (setf (cdr cons) (cons elt (cdr cons)))))))
    (nreverse ret))

    (krause-group '((0) (1 3) (1 2) (4 6) (5 7) (7 8)))
    ((0) (1 2 3) (4 6) (5 8 7))

    (krause-group '((0 1) (1 2) (2 3)))
    (krause-group '((0 1) (0 2) (0 3)))

    So obviously krause wanted both of these lists to produce 1 list
    ((0 3 2 1))

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From HenHanna@21:1/5 to B. Pym on Sat Jun 8 23:23:02 2024
    B. Pym wrote:

    From: Drew Krause
    Subject: rather simple list/set operation
    Date: Tue, 3 Jan 2012 19:01:19 -0600


    Drew Krause wrote:

    Maybe someone can help me with this?

    I start with a list, e.g. ((0) (1 3) (1 2) (4 6) (5 7) (7 8))

    and want all members of intersecting lists to appear in the same
    sublist:
    => ((0) (1 2 3) (4 6) (5 7 8))



    Gauche Scheme:

    (use srfi-1) ; "lset-" functions
    (use srfi-42) ; do-ec

    (define (coalesce lists)
    (define accum '())
    (do-ec (:list x lists)
    (receive
    (miss hit)
    (partition (lambda (y) (null? (lset-intersection equal? x y)))
    accum)
    (set! accum
    (cons (apply lset-union equal? x hit) miss))))
    accum)


    (coalesce '((2 4) (8 9) (4 5 8)))
    ===>
    ((2 9 4 5 8))

    (coalesce '((2 4) (3 9) (5 6) (2 3)))

    ((4 9 2 3) (5 6))

    (coalesce '((0) (1 3) (1 2) (4 6) (5 7) (7 8)))

    ((5 7 8) (4 6) (3 1 2) (0))

    (coalesce '((2 4) (3 9) (5 6) (2 3) (55 66) (0) (66 6)))

    ((5 55 66 6) (0) (4 9 2 3))



    Do-ec and Receive often go together?
    Is there a set of programs (or Problems) or Tutorial for this style of programming?






    Transitive closure constructs the output graph from the
    input graph.
    In computer science, the concept of transitive closure can be thought of
    as constructing a data structure that makes it possible to answer
    reachability questions.

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