[Mupad-combinat-users] finding intersections

[Christopher C. <cc...@mu...>]

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)