Morning all,
There has been some discussion of set partitioning on this group
(http://groups.google.com/groups?hl=en&frame=right&th=5763271444a4fd86&seekm=2l6ue3%24lmq%40hitchcock.dfki.uni-sb.de#link1)
but the solutions offered compute all partitionings of a set while I
need a function which partitions a set according to some equivalence
relation. My (rather half-baked) first effort recurses over the power
set of the set, at each level removing from the power set any subsets
that are equivalent to the car of the set under the supplied
equivalence relation (for my purposes at least it is easy to recover
the remaining sets in a partition):
(defun partition-set (set &key (test #'equivalent?))
"Partition <set> according to an equivalence relation <test>."
(labels ((remove-equivalent-members (set* partitions)
(cond ((null (car set*)) partitions)
(t (remove-equivalent-members
(remove-if #'(lambda (subset)
(funcall test (car set*)
subset))
(cdr set*))
(cons (car set*) partitions))))))
(remove-equivalent-members (power-set set) '())))
(equivalent? set1 set2) --> {t|nil}
(power-set set) --> power-set
The problem is that for sets with more than about 10 members it takes
a very long time to complete the partitioning.
Does anyone have any ideas?
Marcus
In article <···························@posting.google.com>,
Marcus Pearce wrote:
> Morning all,
>
> There has been some discussion of set partitioning on this group
> (http://groups.google.com/groups?hl=en&frame=right&th=5763271444a4fd86&seekm=2l6ue3%24lmq%40hitchcock.dfki.uni-sb.de#link1)
> but the solutions offered compute all partitionings of a set while I
> need a function which partitions a set according to some equivalence
> relation. My (rather half-baked) first effort recurses over the power
> set of the set, at each level removing from the power set any subsets
> that are equivalent to the car of the set under the supplied
> equivalence relation (for my purposes at least it is easy to recover
> the remaining sets in a partition):
>
> (defun partition-set (set &key (test #'equivalent?))
> "Partition <set> according to an equivalence relation <test>."
> (labels ((remove-equivalent-members (set* partitions)
> (cond ((null (car set*)) partitions)
> (t (remove-equivalent-members
> (remove-if #'(lambda (subset)
> (funcall test (car set*)
> subset))
> (cdr set*))
> (cons (car set*) partitions))))))
> (remove-equivalent-members (power-set set) '())))
>
> (equivalent? set1 set2) --> {t|nil}
>
> (power-set set) --> power-set
>
> The problem is that for sets with more than about 10 members it takes
> a very long time to complete the partitioning.
>
> Does anyone have any ideas?
>
> Marcus
Unless I am missing something simple, quite possible I think an
alist/hash data structure would solve your problem. Here is what I
would do to solve what I think is your problem:
create an alist/hash where the key field is the thing you want to test
and the data is the full line, append as needed to the data for other
lines that match the key. Then go through the keys and find all that
match your test and print the data field to get your matches.
You could do the test up front and simply discard the lines that do
not match if you are only going to do one compare per data set.
marc
Marcus Pearce wrote:
> I need a function which partitions a set according to some equivalence
> relation.
I use the following function from time to time:
(defun partition (list analyze &key (categories '() categories-p) (test #'eql))
"Partitions a list by letting the unary function ANALYZE decide in which
category every element of the list belongs. As a second value it returns
a list of categories found. The results are in the same order as in the
given list. The :categories parameter can be used when the exact list
of categories is known in advance. The :test parameter determines how
categories are compared."
(let ((results (make-list (length categories))))
(dolist (object list)
(let* ((category (funcall analyze object))
(pos (position category categories :test test)))
(cond (pos
(push object (elt results pos)))
(t (push category categories)
(push (list object) results)))))
(setq results (mapcar #'nreverse results))
(if categories-p
(values results categories)
(values (nreverse results) (nreverse categories)))))
Here are some examples of how you can use this:
CL-USER 9 > (partition '("a" "few" "different" "distinct" "weird" "words")
#'(lambda (string) (char string 0)))
(("a") ("few") ("different" "distinct") ("weird" "words"))
(#\a #\f #\d #\w)
CL-USER 10 > (partition '(1 2 3 4 5 6 7 8 9)
#'(lambda (n) (mod n 3)))
((1 4 7) (2 5 8) (3 6 9))
(1 2 0)
CL-USER 12 > (partition '(1 3 5) #'oddp :categories '(nil t))
(NIL (1 3 5))
(NIL T)
CL-USER 13 > (partition '(1 3 5) #'oddp)
((1 3 5))
(T)
Feel free to use this code any way you like.
--
Arthur Lemmens
"Marcus Pearce" <··········@city.ac.uk> ha scritto nel messaggio
································@posting.google.com...
> 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.
Cheers
P.
Thanks very much for the replies.
> This is far from efficient, but should be a lot better than wading
> through powersets.
I should have been clearer about this. It is actually the power set
that I would like to partition but I was wondering if there wouldn't
be a way of constructing the partitioned powerset directly from the
original set. As you say, this would be more efficient than wading
through the powerset. Unfortunately, because I am partitioning the
powerset, the only equivalence relation I have available is defined
over pairs of subsets of the original set (i.e., sets in the power
set).
Nontheless, both Pierpaolo's and Arthur's functions can be used to
partition the power set. Here is an example:
1. Pierpaolo's partition:
* (partition (power-set '(0 1 2 3)) #'(lambda (x y) (= (length x)
(length y))))
(((0 1 2 3)) (NIL) ((0 1 2) (0 1 3) (0 2 3) (1 2 3)) ((3) (2) (1) (0))
((0 1) (0 2) (0 3) (1 2) (1 3) (2 3)))
*
2. Arthur's partition:
* (partition (power-set '(0 1 2 3)) #'(lambda (x) x)
:test #'(lambda (x y) (= (length x) (length y))))
(((0 1 2 3)) ((0 1 2) (0 1 3) (0 2 3) (1 2 3))
((0 1) (0 2) (0 3) (1 2) (1 3) (2 3)) ((0) (1) (2) (3)) (NIL))
((0 1 2 3) (0 1 2) (0 1) (0) NIL)
*
This is analagous to what I would like to achieve (although I am using
much larger sets which is why efficiency is a concern). However, since
both these function calls also grovel over the entire powerset, they do
not help much with efficiency. So, my question is this. Would it be
possible to build a partitioned power-set directly from a set but using
an equivalence relation defined over subsets (not elements) of that set?
Cheers
Marcus
If you, do, in fact, need all equivalency classes in the powerset, how are
you hoping to find a solution without groveling through the entire
powerset? Are you only planning on looking at a certain equivalency class
within the powerset (so the rest aren't important)? Are you worried about
the fact that your initial solution runs in O(n^2) worst-case time, where n
is the size of the powerset (worst-case: every set in the powerset is its
own equivalency class)?
Can you give us more information on your equivalency relationship? Does it
admit of some sort of hashing function? Does it induce a partial or total
order?
-Dan Milstein
Marcus Pearce wrote:
>
> Thanks very much for the replies.
>
> > This is far from efficient, but should be a lot better than wading
> > through powersets.
>
> I should have been clearer about this. It is actually the power set
> that I would like to partition but I was wondering if there wouldn't
> be a way of constructing the partitioned powerset directly from the
> original set. As you say, this would be more efficient than wading
> through the powerset. Unfortunately, because I am partitioning the
> powerset, the only equivalence relation I have available is defined
> over pairs of subsets of the original set (i.e., sets in the power
> set).
>
> Nontheless, both Pierpaolo's and Arthur's functions can be used to
> partition the power set. Here is an example:
>
> 1. Pierpaolo's partition:
>
> * (partition (power-set '(0 1 2 3)) #'(lambda (x y) (= (length x)
> (length y))))
> (((0 1 2 3)) (NIL) ((0 1 2) (0 1 3) (0 2 3) (1 2 3)) ((3) (2) (1) (0))
> ((0 1) (0 2) (0 3) (1 2) (1 3) (2 3)))
> *
>
> 2. Arthur's partition:
>
> * (partition (power-set '(0 1 2 3)) #'(lambda (x) x)
> :test #'(lambda (x y) (= (length x) (length y))))
> (((0 1 2 3)) ((0 1 2) (0 1 3) (0 2 3) (1 2 3))
> ((0 1) (0 2) (0 3) (1 2) (1 3) (2 3)) ((0) (1) (2) (3)) (NIL))
> ((0 1 2 3) (0 1 2) (0 1) (0) NIL)
> *
>
> This is analagous to what I would like to achieve (although I am using
> much larger sets which is why efficiency is a concern). However, since
> both these function calls also grovel over the entire powerset, they do
> not help much with efficiency. So, my question is this. Would it be
> possible to build a partitioned power-set directly from a set but using
> an equivalence relation defined over subsets (not elements) of that set?
>
> Cheers
> Marcus
--
Dan Milstein // ······@shore.net
"Marcus Pearce" <··········@city.ac.uk> ha scritto nel messaggio
·································@posting.google.com...
> This is analagous to what I would like to achieve (although I am using
> much larger sets which is why efficiency is a concern). However, since
> both these function calls also grovel over the entire powerset, they do
> not help much with efficiency. So, my question is this. Would it be
> possible to build a partitioned power-set directly from a set but using
> an equivalence relation defined over subsets (not elements) of that set?
It is not clear what equivalence relations are you interested in.
If these relations are arbitrary functions passed as parameters,
then I don't see how you can omit generating the powersets.
If you need only a particular equivalence relation, then almost
certainly is possible to do better.
Cheers
P.