Package net.sf.tweety.commons.util

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.