org.matheclipse.combinatoric

Class MultisetCombinationIterator

java.lang.Object

org.matheclipse.combinatoric.MultisetCombinationIterator

All Implemented Interfaces:

java.util.Iterator<int[]>

public class MultisetCombinationIterator
extends java.lang.Object
implements java.util.Iterator<int[]>

Combinations of a multiset

These are the combinations of k elements chosen from a sorted int[] array, that can contain duplicates (a multiset).

For example, given the multiset {0, 1, 1, 2, 2, 2, 3}, the 4-combinations are:

 [0, 1, 1, 2]
 [0, 1, 1, 3]
 [0, 1, 2, 2]
 [0, 1, 2, 3]
 [0, 2, 2, 2]
 [0, 2, 2, 3]
 [1, 1, 2, 2]
 [1, 1, 2, 3]
 [1, 2, 2, 2]
 [1, 2, 2, 3]
 [2, 2, 2, 3]
 

This algorithm produces the combinations in lexicographic order, with the elements in each combination in increasing order.

Begin with the first combination, which is the first k elements of the multiset ([0, 1, 1, 2] in the example above), and then at each step:

1. Find the rightmost element that is less than the maximum value it can have (which is the element in the multiset that is the same distance from the right).
2. Replace it with the first multiset element greater than it.
3. Replace the remainder of the combination with the elements that follow the replacement in the multiset.

See: martinbroadhurst.com Combinations of a Multiset

Constructor Summary

Constructors

Constructor and Description
MultisetCombinationIterator(int[] multiset, int k) Combinations of a multiset

Method Summary

Modifier and Type	Method and Description
boolean	hasNext()
int[]	next()
void	remove() Throws an UnsupportedOperationException
void	reset()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Iterator

forEachRemaining

Constructor Detail

MultisetCombinationIterator

public MultisetCombinationIterator(int[] multiset,
                                   int k)

Combinations of a multiset

These are the combinations of k elements chosen from a sorted int[] array, that can contain duplicates (a multiset).

Method Detail

reset

public void reset()

next

public int[] next()

Specified by:

next in interface java.util.Iterator<int[]>

See Also:

Iterator.next()

hasNext

public final boolean hasNext()

Specified by:

hasNext in interface java.util.Iterator<int[]>

See Also:

Iterator.hasNext()

remove

public void remove()

Throws an UnsupportedOperationException

Specified by:

remove in interface java.util.Iterator<int[]>