[GAP Forum] Atoms of a boolean algebra of sets

[Johannes Hahn]

Thank you very much, Stefan and Jean. That solves my problem.

 

Best wishes

Johannes.

 

Von: Stefan Kohl <sk239 at st-andrews.ac.uk> 
Gesendet: Dienstag, 26. Februar 2019 01:07
An: Johannes Hahn <johannes.hahn at uni-jena.de>; forum at gap-system.org
Betreff: Re: [GAP Forum] Atoms of a boolean algebra of sets

 

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 < <mailto:johannes.hahn at uni-jena.de> johannes.hahn at uni-jena.de>
Sent: Tuesday, February 26, 2019 12:01:15 AM
To:  <mailto:forum at gap-system.org> 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
 <mailto:Forum at gap-system.org> Forum at gap-system.org
 <https://mail.gap-system.org/mailman/listinfo/forum> https://mail.gap-system.org/mailman/listinfo/forum