Package org.cis1200

Class ProbabilityDistribution<T extends Comparable<T>>

java.lang.Object
org.cis1200.ProbabilityDistribution<T>
class ProbabilityDistribution<T extends Comparable<T>> extends Object
This class represents a probability distribution over a type T as a map from T values to integers. We can think of this map as a "histogram" of the frequency of occurrences observed for T values. This class is implemented for you.

We can build a probability distribution by "recording" new occurrences of a value. For instance, if we want to build a probability distribution over String values, we might record the following occurrences: record("a"); record("b"); record("a"); record("a"); record("c")

The resulting distribution would map "a" to a frequency count of 3, and "b" and "c" both to 1, since we recorded only one of each.

We can sample (a.k.a. "pick") an element from the probability distribution at random, based on the frequency information in the records.

For instance, given the distribution above, we would pick "a" with 3/5 probability and each of "b" and "c" with 1/5 probability. Of the 5 total observations, 3 were "a". (Assuming that the number generator is truly random -- a non-random number generator, which is useful for testing, might yield different outcomes.)

  • Constructor Summary

    Constructors
    Constructor
    Description
    ProbabilityDistribution()
    Constructs an empty distribution.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    count(T t)
    Counts the number of occurrences of an element in the ProbabilityDistribution
    Map<T,Integer>
    getRecords()
    Exposes the internal representation of the ProbabilityDistribution as a Map for testing purposes.
    int
    getTotal()
    Total number of instances that have been added via record().
    int
    index(T element)
    Returns the index of the element such that pick(index) will return the element
    Set<T>
    keySet()
     
    T
    pick(int index)
    Picks an element out of the Probability Distribution non-randomly according to the provided index.
    T
    pick(NumberGenerator generator)
    Picks an instance of the ProbabilityDistribution according to the provided NumberGenerator.
    void
    record(T t)
    Add an instance to the ProbabilityDistribution.
    String
    toString()
    Print the probability distribution

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • ProbabilityDistribution

      public ProbabilityDistribution()
      Constructs an empty distribution.

  • Method Details

    • getTotal

      public int getTotal()
      Total number of instances that have been added via record().
      Returns:
      an int representing the number of records in the ProbabilityDistribution.

    • getRecords

      public Map<T,Integer> getRecords()
      Exposes the internal representation of the ProbabilityDistribution as a Map for testing purposes.
      Returns:
      a copy of the ProbabilityDistribution's internal Map

    • pick

      public T pick(NumberGenerator generator)
      Picks an instance of the ProbabilityDistribution according to the provided NumberGenerator. If the provided NumberGenerator is random, then the resulting T values are chosen with probability proportional to the frequency that they have been recorded.
      Parameters:
      generator - - uses the generator to pick a particular element in the ProbabilityDistribution.
      Returns:
      the chosen element of the ProbabilityDistribution
      Throws:
      IllegalArgumentException - if a number received from the generator is less than zero or greater than the total number of records in the PD
      NoSuchElementException - if the generator can't generate numbers less than the number of records in the ProbabilityDistribution

    • pick

      public T pick(int index)
      Picks an element out of the Probability Distribution non-randomly according to the provided index. To determine an element's index, we treat the distribution as an array where each element occurs a number of times according to its value.

      For example, given the distribution printed as: 

       { "banana": 2  "chair":1  "table":1 }
      We think of it as an array of length 4, containing the elements at the indices given: 
       {    0   ,     1   ,    2   ,    3   }
 {"banana", "banana", "chair", "table"}
      Parameters:
      index - - use this to pick a particular element in the ProbabilityDistribution. Must not be more than the number of elements in the ProbabilityDistribution.
      Returns:
      the chosen element of the ProbabilityDistribution
      Throws:
      IllegalArgumentException - if index is less than zero or greater than the total number of records in the PD

    • record

      public void record(T t)
      Add an instance to the ProbabilityDistribution. If the element already exists in the ProbabilityDistribution, it will increment the number of occurrences of that element.
      Parameters:
      t - - an element to add to the distribution
      Throws:
      IllegalArgumentException - when t is null

    • count

      public int count(T t)
      Counts the number of occurrences of an element in the ProbabilityDistribution
      Parameters:
      t - - the element you want to get the count of
      Returns:
      the number of occurrences of the provided element in the ProbabilityDistribution
      Throws:
      IllegalArgumentException - when t is not in the distribution (i.e, it has not been previously recorded)

    • keySet

      public Set<T> keySet()
      Returns:
      a set containing all elements in the ProbabilityDistribution

    • index

      public int index(T element)
      Returns the index of the element such that pick(index) will return the element
      Parameters:
      element - - the element to find the index of
      Returns:
      the index of the specified element
      Throws:
      IllegalArgumentException - if the element is not in the distribution

    • toString

      public String toString()
      Print the probability distribution
      Overrides:
      toString in class Object