org.ddogleg.combinatorics

Class Combinations<T>

java.lang.Object

org.ddogleg.combinatorics.Combinations<T>

public class Combinations<T>
extends java.lang.Object

Computes the combinations of size k given a set S of size N. This can be done in the forward or reverse direction. A combination is defined is a unique subset of a list in which order does not mater. This is different from a permutation where order does matter.

The bucket is used to refer to the output set of size k that is the current combination. Elements outside the bucket are all elements not currently in the bucket.

Below is an example of a combination.

 List = 012345
 k = 3;

 012
 013
 014
 015
 023
 024
 025
 034
 035
 045
 123
 124
 125
 134
 135
 145
 234
 235
 245
 345
 

Constructor Summary

Constructors

Constructor and Description
Combinations()
Combinations(java.util.List<T> a, int bucketSize) Constructor where the list and combinations is specified

Method Summary

Modifier and Type	Method and Description
long	computeTotalCombinations() The number of combinations is, n!/(k!*(n-k)!, where n is number of elements, k is the number of bins, and ! is factorial.
T	get(int i) Returns element 'i' in the bucket.
java.util.List<T>	getBucket(java.util.List<T> storage) Extracts the entire bucket.
int	getBucketSize() Returns the size of the bucket/output set
java.util.List<T>	getOutside(java.util.List<T> storage) This returns all the items that are not currently inside the bucket
void	init(java.util.List<T> list, int bucketSize) Initialize with a new list and bucket size
boolean	next() This will shuffle the elements in and out of the bins.
boolean	previous() Undoes the previous combination computed by next().

Methods inherited from class java.lang.Object

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

Constructor Detail

Combinations

public Combinations(java.util.List<T> a,
                    int bucketSize)

Constructor where the list and combinations is specified

Parameters:

a - List of symbols

bucketSize - Size of the bucket

Combinations

public Combinations()

Method Detail

init

public void init(java.util.List<T> list,
                 int bucketSize)

Initialize with a new list and bucket size

Parameters:

list - List which is to be symbols

bucketSize - Size of the bucket

next

public boolean next()

This will shuffle the elements in and out of the bins. When all combinations have been exhausted an ExhaustedException will be thrown.

Returns:

true if the next combination was successfully found or false is it has been exhausted

previous

public boolean previous()

Undoes the previous combination computed by next().

Returns:

true if the combination was successfully undone or false is is back to the original state

computeTotalCombinations

public long computeTotalCombinations()

The number of combinations is, n!/(k!*(n-k)!, where n is number of elements, k is the number of bins, and ! is factorial.

Returns:

Total number

getBucketSize

public int getBucketSize()

Returns the size of the bucket/output set

Returns:

Size of bucket

get

public T get(int i)

Returns element 'i' in the bucket.

Parameters:

i - which element

Returns:

the element

getBucket

public java.util.List<T> getBucket(java.util.List<T> storage)

Extracts the entire bucket. Will add elements to the provided list or create a new one

Parameters:

storage - Optional storage. If null a list is created. clear() is automatically called.

Returns:

List containing the bucket

getOutside

public java.util.List<T> getOutside(java.util.List<T> storage)

This returns all the items that are not currently inside the bucket

Parameters:

storage - Optional storage. If null a list is created. clear() is automatically called.

Returns:

List containing the bucket