|
From: Christopher C. <cc...@mu...> - 2006-11-30 08:50:52
|
Salvete,
this may be trivial to combinatorists (I actually hope so), but I am
none, so I don't see it right away: Given a finite list of finite sets,
is there some short incantation that gives me the nontrivial
intersections of these lists, preferably without computing all 2^n
combinations of sets and intersecting them? I.e., a faster way of doing
intersections :=
proc(l : Type::ListOf(DOM_SET))
local i, ret;
begin
ret := select(combinat::subsets(nops(l)),
s -> nops(s) > 1);
ret := map(ret, s -> [s, _intersect(l[i] $ i in s)]);
ret := select(ret, s -> nops(s[2])>0);
end_proc:
intersections([{a}, {b}, {a,b,c}])
[[{1, 3}, {a}], [{2, 3}, {b}]]
intersections([{a}, {a, b}, {a, b, c}])
[[{1, 2}, {a}], [{1, 3}, {a}], [{2, 3}, {a, b}],
[{1, 2, 3}, {a}]]
Actually, I'm primarily interested in the maximal combinations of sets,
so if in the last example the result was [[{2, 3}, {a, b}], [{1, 2, 3},
{a}]], that might be even better.
It's obviously possible to get these results with fewer calculations,
since adding more sets to a selection that already has an empty
intersection won't lead to new results. Does the combinat library have
something helpful for me?
Bonus question: What about multisets? I can emulate them with sets, as
in {[a, 1], [b, 1], [b, 2]}, but if the code could handle them directly,
that would probably be more readable and faster.
(In case you are interested: I'm trying to find common factors in a
sum, for simplification.)
Regards,
Christopher
(hoping he is actually subscribed to the users' list)
|