org.jamesframework.core.util

Class SubsetIterator<T>

java.lang.Object

org.jamesframework.core.util.SubsetIterator<T>

Type Parameters:

T - type of elements in set and generated subsets

All Implemented Interfaces:

Iterator<Set<T>>

public class SubsetIterator<T>
extends Object
implements Iterator<Set<T>>

A subset iterator generates all possible subsets of a given set, within the imposed size range.

The implemented generation algorithm is the revolving door algorithm from "Combinatorial Algorithms: Generation, Enumeration and Search", Donald Kreher and Douglas Stinson, CRC Press, 1999 (chapter 2, p. 43-52). This algorithm generates k-subsets in a specific minimal change ordering called the revolving door ordering.

Author:

Herman De Beukelaer

Constructor Summary

Constructors

Constructor and Description
SubsetIterator(Set<T> items, int fixedSubsetSize) Create a subset iterator that generates all subsets of the given set, with a fixed size.
SubsetIterator(Set<T> items, int minSubsetSize, int maxSubsetSize) Create a subset iterator that generates all subsets of the given set, within the imposed size range.

Method Summary

Modifier and Type	Method and Description
boolean	hasNext() Checks whether more subsets are to be generated.
Set<T>	next() Generate the next subset in a newly allocated LinkedHashSet.
Collection<T>	next(Collection<T> subset) Fill the given collection with the items from the next subset.

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, remove

Constructor Detail

SubsetIterator

public SubsetIterator(Set<T> items,
                      int minSubsetSize,
                      int maxSubsetSize)

Create a subset iterator that generates all subsets of the given set, within the imposed size range.

Parameters:

items - set of items to select from

minSubsetSize - minimum subset size

maxSubsetSize - maximum subset size

Throws:

NullPointerException - if items is null

IllegalArgumentException - if items is empty, minSubsetSize < 0, minSubsetSize > |IDs|, or minSubsetSize > maxSubsetSize

SubsetIterator

public SubsetIterator(Set<T> items,
                      int fixedSubsetSize)

Create a subset iterator that generates all subsets of the given set, with a fixed size.

Parameters:

items - set of items to select from

fixedSubsetSize - fixed subset size

Throws:

NullPointerException - if items is null

IllegalArgumentException - if items is empty, fixedSubsetSize < 0, or fixedSubsetSize > |items|

Method Detail

hasNext

public boolean hasNext()

Checks whether more subsets are to be generated.

Specified by:

hasNext in interface Iterator<Set<T>>

Returns:

false if all possible subsets of all valid sizes have already been generated, else true

next

public Collection<T> next(Collection<T> subset)

Fill the given collection with the items from the next subset. The collection is not cleared so already contained items will be retained. A reference to this same collection is returned after it has been modified.

To store the next subset in a newly allocated LinkedHashSet the alternative method next() may also be used.

Parameters:

subset - collection to fill with items from next generated subset

Returns:

reference to given collection, after it has been filled with the items from the next subset

Throws:

NoSuchElementException - if there is no next subset to be generated

next

public Set<T> next()

Generate the next subset in a newly allocated LinkedHashSet.

Specified by:

next in interface Iterator<Set<T>>

Returns:

next subset stored in newly allocated LinkedHashSet.

Throws:

NoSuchElementException - if there is no next subset to be generated