Class SetTools<E>

  • Type Parameters:
    E - the type of elements

    public class SetTools<E>
    extends java.lang.Object
    This class provides some methods for set operations.
    Author:
    Matthias Thimm
    • Constructor Summary

      Constructors 
      Constructor Description
      SetTools()  
    • Method Summary

      Modifier and Type Method Description
      java.util.Set<java.util.Set<java.util.Set<E>>> getBipartitions​(java.util.Set<E> set)
      Computes every bipartition of the given set, e.g.
      java.util.Set<E> getUnion​(java.util.Set<java.util.Set<E>> sets)
      Returns the union of the set of sets.
      boolean hasEmptyIntersection​(java.util.Set<java.util.Set<E>> sets)
      Checks whether the given set of sets has an empty intersection
      java.util.Set<java.util.Set<java.util.Collection<E>>> independentSets​(java.util.Set<java.util.Collection<E>> sets, int cardinality)
      Returns all independent sets of the given cardinality of the given set of sets.
      java.util.Set<java.util.Set<E>> irreducibleHittingSets​(java.util.Set<java.util.Set<E>> sets)
      Computes the set of irreducible hitting sets of "sets".
      boolean isIndependent​(java.util.Set<java.util.Collection<E>> set)
      Checks whether the given set of sets is independent, i.e.
      java.util.Set<java.util.Set<E>> permutations​(java.util.Set<java.util.Set<E>> partitions)
      Computes all permutations of elements in partitions as follows.
      E randomElement​(java.util.Collection<E> set)
      Picks one element uniformly at random from the set (not very efficient).
      java.util.Set<java.util.Set<E>> subsets​(java.util.Collection<? extends E> elements)
      This method computes all subsets of the given set of elements of class "E".
      java.util.Set<java.util.Set<E>> subsets​(java.util.Collection<? extends E> elements, int size)
      This method computes all subsets of the given set of elements of class "E" with the given size.
      java.util.Set<E> symmetricDifference​(java.util.Collection<E> s, java.util.Collection<E> t)
      Returns the symmetric difference of the two sets s and t, i.e.
      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • SetTools

        public SetTools()
    • Method Detail

      • subsets

        public java.util.Set<java.util.Set<E>> subsets​(java.util.Collection<? extends E> elements)
        This method computes all subsets of the given set of elements of class "E".
        Parameters:
        elements - a set of elements of class "E".
        Returns:
        all subsets of "elements".
      • subsets

        public java.util.Set<java.util.Set<E>> subsets​(java.util.Collection<? extends E> elements,
                                                       int size)
        This method computes all subsets of the given set of elements of class "E" with the given size.
        Parameters:
        elements - a set of elements of class "E".
        size - some int.
        Returns:
        all subsets of "elements" of the given size.
      • permutations

        public java.util.Set<java.util.Set<E>> permutations​(java.util.Set<java.util.Set<E>> partitions)
        Computes all permutations of elements in partitions as follows. For any set A in the result and any set B in partitions it holds, that exactly one element of B is in A. For example
        permutations({{a,b},{c,d,e},{f}})
        equals to
        {{a,c,f},{b,c,f},{a,d,f},{b,d,f},{a,e,f},{b,e,f}}
        Parameters:
        partitions - a set of sets of E.
        Returns:
        a set of sets of E.
      • irreducibleHittingSets

        public java.util.Set<java.util.Set<E>> irreducibleHittingSets​(java.util.Set<java.util.Set<E>> sets)
        Computes the set of irreducible hitting sets of "sets". A hitting set H is a set that has a non-empty intersection with every set in "sets". H is irreducible if no proper subset of H is a hitting set.
        Parameters:
        sets - a set of sets
        Returns:
        the set of all irreducible hitting sets of "sets"
      • hasEmptyIntersection

        public boolean hasEmptyIntersection​(java.util.Set<java.util.Set<E>> sets)
        Checks whether the given set of sets has an empty intersection
        Parameters:
        sets - some set of sets
        Returns:
        true iff the all sets have an empty intersection.
      • getUnion

        public java.util.Set<E> getUnion​(java.util.Set<java.util.Set<E>> sets)
        Returns the union of the set of sets.
        Parameters:
        sets - some set of sets
        Returns:
        the union of the set.
      • getBipartitions

        public java.util.Set<java.util.Set<java.util.Set<E>>> getBipartitions​(java.util.Set<E> set)
        Computes every bipartition of the given set, e.g. for a set {a,b,c,d,e,f} this method returns a set containing for example {{a,b,c,d,e},{f}} and {{a,b,c,},{d,e,f}} and {{a,b,c,d,e,f},{}} and {{a,d,e},{b,c,f}}.
        Parameters:
        set - a set of E
        Returns:
        the set of all bipartitions of the given set.
      • symmetricDifference

        public java.util.Set<E> symmetricDifference​(java.util.Collection<E> s,
                                                    java.util.Collection<E> t)
        Returns the symmetric difference of the two sets s and t, i.e. it returns (s \cup t) \setminus (s \cap t).
        Parameters:
        s - some set
        t - some set
        Returns:
        the symmetric difference of the two sets
      • independentSets

        public java.util.Set<java.util.Set<java.util.Collection<E>>> independentSets​(java.util.Set<java.util.Collection<E>> sets,
                                                                                     int cardinality)
        Returns all independent sets of the given cardinality of the given set of sets. A set M={M1,...,Mk} is an independent set of N={N1,...,Nl} if M\subseteq N and for all i,j, i\neq j, Mi\cap Mj=\emptyset.
        This method uses a brute force approach to determine these sets.
        Parameters:
        sets - a set of sets
        cardinality - an int
        Returns:
        all independent sets of the given cardinality of the given set of sets
      • isIndependent

        public boolean isIndependent​(java.util.Set<java.util.Collection<E>> set)
        Checks whether the given set of sets is independent, i.e. whether all pairs of sets are disjoint.
        Parameters:
        set - a set of sets
        Returns:
        "true" if the given set of sets is independent.
      • randomElement

        public E randomElement​(java.util.Collection<E> set)
        Picks one element uniformly at random from the set (not very efficient).
        Parameters:
        set - some set
        Returns:
        one element from the set.