Package org.tweetyproject.commons.util

Class SetTools<E>

java.lang.Object

org.tweetyproject.commons.util.SetTools<E>

Type Parameters:

E - the type of elements

public class SetTools<E>
extends Object

This class provides some methods for set operations.

Author:

Matthias Thimm

Constructor Summary

Constructors

Constructor	Description
SetTools()	Default Constructor

Method Summary

Modifier and Type	Method	Description
Set<Set<Set<E>>>	getBipartitions(Set<E> set)	Computes every bipartition of the given set, e.g.
Set<E>	getUnion(Set<Set<E>> sets)	Returns the union of the set of sets.
boolean	hasEmptyIntersection(Set<Set<E>> sets)	Checks whether the given set of sets has an empty intersection
Set<Set<Collection<E>>>	independentSets(Set<Collection<E>> sets, int cardinality)	Returns all independent sets of the given cardinality of the given set of sets.
Set<Set<E>>	irreducibleHittingSets(Set<Set<E>> sets)	Computes the set of irreducible hitting sets of "sets".
boolean	isIndependent(Set<Collection<E>> set)	Checks whether the given set of sets is independent, i.e.
Set<Set<E>>	permutations(Set<Set<E>> partitions)	Computes all permutations of elements in partitions as follows.
static <E> Set<Set<E>>	powerSet(Set<E> originalSet)	Generates the power set of a given set.
E	randomElement(Collection<E> set)	Picks one element uniformly at random from the set (not very efficient).
Set<Set<E>>	subsets(Collection<? extends E> elements)	This method computes all subsets of the given set of elements of class "E".
Set<Set<E>>	subsets(Collection<? extends E> elements, int size)	This method computes all subsets of the given set of elements of class "E" with the given size.
Set<E>	symmetricDifference(Collection<E> s, 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 Details

SetTools

public SetTools()

Default Constructor

Method Details

subsets

public Set<Set<E>> subsets(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 Set<Set<E>> subsets(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 Set<Set<E>> permutations(Set<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 Set<Set<E>> irreducibleHittingSets(Set<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(Set<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 Set<E> getUnion(Set<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 Set<Set<Set<E>>> getBipartitions(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 Set<E> symmetricDifference(Collection<E> s,
 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 Set<Set<Collection<E>>> independentSets(Set<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(Set<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(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.

powerSet

public static <E> Set<Set<E>> powerSet(Set<E> originalSet)

Generates the power set of a given set. The power set of a set is the set of all possible subsets, including the empty set and the set itself.

For example, the power set of `{a, b, c}` is `{{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}`.

Note: The method uses recursion to generate the power set, so it may not be suitable for very large sets due to potential stack overflow or performance concerns.

Type Parameters:

E - the type of elements in the original set.

Parameters:

originalSet - the original set for which the power set is to be generated.

Returns:

a set of sets representing the power set of the original set.