[GAP Forum] Atoms of a boolean algebra of sets

[Stefan Kohl]

Dear Johannes,


As to your second question: I think it should be straightforward to adapt RCWA's internal function

'CommonRefinementOfPartitionsOfZ_NC' for this purpose. That function computes the common refinement of a set of partitions of the integers into finitely many residue classes:


#############################################################################
##
#F  CommonRefinementOfPartitionsOfZ_NC( <partitions> ) . . special case R = Z
##
InstallGlobalFunction( CommonRefinementOfPartitionsOfZ_NC,

  function ( partitions )

    local  table, partition, mods, res, m,
           pow, mj, r, i, j, k;

    mods  := List(partitions,P->List(P,Mod));
    res   := List(partitions,P->List(P,Residues));
    m     := Lcm(Concatenation(mods));
    table := List([1..m],i->0);
    pow   := 1;
    for i in [1..Length(partitions)] do
      for j in [1..Length(partitions[i])] do
        mj := mods[i][j];
        for r in res[i][j] do
          for k in [r,r+mj..r+(Int(m/mj)-1)*mj] do
            table[k+1] := table[k+1] + pow;
          od;
        od;
        pow := pow + pow;
      od;
    od;
    partition := EquivalenceClasses([1..m],r->table[r]);
    return Set(List(partition,r->ResidueClassUnion(Integers,m,r-1)));
  end );


Hope this helps,


    Stefan


________________________________
From: Johannes Hahn <johannes.hahn at uni-jena.de>
Sent: Tuesday, February 26, 2019 12:01:15 AM
To: forum at gap-system.org
Subject: [GAP Forum] Atoms of a boolean algebra of sets

Dear forum,



Let’s say a have a list of subsets of a fixed finite set $\Omega$. Is there a nice and easy way to find the atoms of the Boolean algebra generated by these sets? Of course, I could implement this by hand, but it seems to me that something like this probably already exists and I simply had bad luck finding it.



A related question: Let’s say I have a list of partitions of $\Omega$ (i.e. a set of pairwise disjoint subsets that cover all of $\Omega$). Is there a nice and easy way to find the common refinement of all these partitions?



Best wishes

Johannes Hahn.

_______________________________________________
Forum mailing list
Forum at gap-system.org
https://mail.gap-system.org/mailman/listinfo/forum