Re: Set Partitioning

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))))))