Package org.ddogleg.combinatorics

Class Combinations<T>

java.lang.Object
org.ddogleg.combinatorics.Combinations<T>
public class Combinations<T> extends 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

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected List<T>
    a
     
    protected int[]
    bins
     
    protected int
    c
     
    protected int
    k
     
    protected int
    N
     
    protected int
    state
     

  • Constructor Summary

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

  • Method Summary

    Modifier and Type
    Method
    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.
    static long
    computeTotalCombinations(int setSize, int comboSize)
     
    T
    get(int i)
    Returns element 'i' in the bucket.
    List<T>
    getBucket(@Nullable List<T> storage)
    Extracts the entire bucket.
    int
    getBucketSize()
    Returns the size of the bucket/output set
    List<T>
    getOutside(@Nullable List<T> storage)
    This returns all the items that are not currently inside the bucket
    final void
    init(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

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

  • Field Details

    • a

      protected List<T> a

    • N

      protected int N

    • k

      protected int k

    • bins

      protected int[] bins

    • c

      protected int c

    • state

      protected int state

  • Constructor Details

    • Combinations

      public Combinations(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 Details

    • init

      public final void init(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

    • computeTotalCombinations

      public static long computeTotalCombinations(int setSize, int comboSize)

    • 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 List<T> getBucket(@Nullable @Nullable 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 List<T> getOutside(@Nullable @Nullable 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