1. Forum
  2. USENET
  3. comp.lang.scheme

  • Re: Set Partitioning

    From B. Pym@Nobody447095@here-nor-there.org to comp.lang.lisp,comp.lang.scheme on Sat Jul 5 15:23:32 2025
    From Newsgroup: comp.lang.scheme

    Pierpaolo BERNARDI wrote:

    I need a function which partitions a set according to
    some equivalence relation.

    Is this what you need?

    (defun partition (set equivalence)
    (loop for s = set then (set-difference s eqv-class :test equivalence)
    while s
    for eqv-class = (remove-if-not (lambda (x)
    (funcall equivalence x (first s)))
    s)
    collect eqv-class))


    CL-USER 57 > (partition '(aabs qweq rew er rtyrtyr s q w e foo bar)
    (lambda (x y) (= (length (string x))
    (length (string y)))))
    ((AABS QWEQ) (BAR FOO REW) (ER) (E W Q S) (RTYRTYR))


    This is far from efficient, but should be a lot better than wading
    through powersets.

    Gauche Scheme

    Using an association list.

    (use gauche.sequence) ;; size-of

    (let ((bag '()))
    (for-each
    (lambda(s)
    (set! bag
    (update-alist bag (size-of (x->string s)) s cons '())))
    '(aabs qweq rew er rtyrtyr s q w e foo bar))
    bag)

    ===>
    ((3 bar foo rew) (4 qweq aabs) (2 er) (1 e w q s) (7 rtyrtyr))

    Given:

    ;; Non-destructive.
    (define (update-alist alist k v :optional (func #f) (default 0))
    (define (alter-entry e)
    (if func
    (let ((new-v (func v (if e (cdr e) default))))
    (cons k new-v))
    (cons k v)))
    (let go ((the-list alist) (seen '()))
    (cond ((null? the-list) (cons (alter-entry #f) seen))
    ((equal? k (caar the-list))
    (append (cons (alter-entry (car the-list)) seen)
    (cdr the-list)))
    (#t (go (cdr the-list) (cons (car the-list) seen))))))
    --- Synchronet 3.21a-Linux NewsLink 1.2