Class RandomSubsetIterator<T>

  • Type Parameters:
    T - The element class which is iterated.
    All Implemented Interfaces:
    java.util.Iterator<java.util.Set<T>>

    public class RandomSubsetIterator<T>
    extends SubsetIterator<T>
    Iterates over all subsets of a given sets in a random order.
    Author:
    Matthias Thimm
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private double allSubsets
      Only used when avoidDuplicats is set to true.
      private boolean avoidDuplicates
      Whether to avoid duplicates in the iteration.
      private long generatedSubsets
      Only used when avoidDuplicats is set to true.
      private java.util.Random random
      The random number generator.
      private java.util.List<T> set
      The set over which subsets are iterated.
      private boolean switched
      Only used when avoidDuplicats is set to true.
      private java.util.Set<java.util.BitSet> temp
      Only used when avoidDuplicats is set to true.
    • Constructor Summary

      Constructors 
      Constructor Description
      RandomSubsetIterator​(java.util.Set<T> set, boolean avoidDuplicates)
      Creates a new subset iterator for the given set.
    • Method Summary

      Modifier and Type Method Description
      private java.util.BitSet generate​(int length, boolean checkForDuplicates)
      Generates a new bit set of the given length.
      private java.util.BitSet generateRandomly​(int length)
      Generates a random bit set of the given length.
      boolean hasNext()  
      private void increment​(java.util.BitSet bitSet)
      Increments the given bit set
      java.util.Set<T> next()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
      • Methods inherited from interface java.util.Iterator

        forEachRemaining
    • Field Detail

      • set

        private java.util.List<T> set
        The set over which subsets are iterated.
      • avoidDuplicates

        private boolean avoidDuplicates
        Whether to avoid duplicates in the iteration.
      • random

        private java.util.Random random
        The random number generator.
      • temp

        private java.util.Set<java.util.BitSet> temp
        Only used when avoidDuplicats is set to true. Then this set contains all (representations of) subsets already generated (if those are less than half the number of all subsets) or the subsets not generated yet (otherwise).
      • generatedSubsets

        private long generatedSubsets
        Only used when avoidDuplicats is set to true. The number of already generated subsets.
      • allSubsets

        private double allSubsets
        Only used when avoidDuplicats is set to true. The number of all subsets.
      • switched

        private boolean switched
        Only used when avoidDuplicats is set to true. Whether the mode of using this.temp has been switched.
    • Constructor Detail

      • RandomSubsetIterator

        public RandomSubsetIterator​(java.util.Set<T> set,
                                    boolean avoidDuplicates)
        Creates a new subset iterator for the given set.
        Parameters:
        set - some set.
        avoidDuplicates - whether to avoid duplicates in the iteration. NOTE: setting this value to true might increase computation time and needed space drastically.
    • Method Detail

      • hasNext

        public boolean hasNext()
        Specified by:
        hasNext in interface java.util.Iterator<T>
        Specified by:
        hasNext in class SubsetIterator<T>
      • next

        public java.util.Set<T> next()
        Specified by:
        next in interface java.util.Iterator<T>
        Specified by:
        next in class SubsetIterator<T>
      • increment

        private void increment​(java.util.BitSet bitSet)
        Increments the given bit set
        Parameters:
        bitSet - some bit set.
      • generate

        private java.util.BitSet generate​(int length,
                                          boolean checkForDuplicates)
        Generates a new bit set of the given length. If checkForDuplicates is true then the all bit sets in this.temp are regarded as already being generated and the new one will be different from all of those. Furthermore, the new bit set is added to this.temp. If checkForDuplicates is false, the new bit set will be chosen from this.temp and removed there.
        Parameters:
        length - the length of the bit set.
        checkForDuplicates - whether to check for duplicates (see above).
        Returns:
        a bit set.
      • generateRandomly

        private java.util.BitSet generateRandomly​(int length)
        Generates a random bit set of the given length.
        Parameters:
        length - some length.
        Returns:
        a random bit set.