Package InversionTest :: Module InversionDistribution
[hide private]
[frames] | no frames]

Module InversionDistribution

Properties of the permutations (null distribution) for inversions of a totally-ordered sequence. Includes: max, mean, variance, similarity, correlation, and counts of permutations with k inversions (called I_n[k] in some literature).

Author: Benjamin D. Nye License: Apache License V2.0

Classes [hide private]
  InversionCountsCache
A cache for managing stored inversion count calculations
Functions [hide private]
list of int
_directCalcRawInversionCounts(n, startingPoint=None, cache=True)
Calculate the count of the number of permutations with k inversions, as a vector of Inv(n,k) in the form [Inv(n,0), Inv(n,1), ..., Inv(n,k_max)] where n is the length of the sequence and k_max is the maximum inversions.
float
correlationByInversions(inversions, maxInversions)
Correlation between sequences, given the inversions and max possible A correlation of -1 is the worst, while 1 is the best.
int
maxInversions(n)
Maximum inversions for a permutation of a sequence of n elements Note: This will always return an integer
float
meanOfInversions(n)
Mean (expected) inversions for a permutation of a sequence of n elements Note: This returns a float, as the expectation maybe fractional.
list of int
rawInversionCounts(n)
Get the count of the number of permutations with k inversions, as a vector of Inv(n,k) in the form [Inv(n,0), Inv(n,1), ..., Inv(n,k_max)] where n is the length of the sequence and k_max is the maximum inversions Note: This implementation uses the InversionCountsCache to boost speed
float
similarityByInversions(inversions, maxInversions)
Similarity between sequences, given the inversions and max possible A similarity of 0 is the worst, while 1 is the best.
float
varianceOfInversions(n)
Variance of inversions for a permutation of a sequence of n elements Note: This returns a float, as the variance maybe fractional.
Variables [hide private]
  __loader__ = <zipimporter object "C:\Python27\lib\site-package...
  __package__ = None
Function Details [hide private]

_directCalcRawInversionCounts(n, startingPoint=None, cache=True)

 

Calculate the count of the number of permutations with k inversions, as a vector of Inv(n,k) in the form [Inv(n,0), Inv(n,1), ..., Inv(n,k_max)] where n is the length of the sequence and k_max is the maximum inversions. Note: This implementation can be bootstrapped using a startingPoint, to avoid calculating known inversions (as the algorithm works through iterative transforms)

Parameters:
  • n (int) - Number of elements in the sequence
  • startingPoint (tuple of (int, list of int)) - Pair of (x, rawInversionCounts(x)) where x<n. Used to bootstrap the calculation.
  • cache (bool) - If True, cache the calculated values. Else, ignore the cache.
Returns: list of int
List of inversion counts, where index k gives the # of permutations with k inversions

correlationByInversions(inversions, maxInversions)

 

Correlation between sequences, given the inversions and max possible A correlation of -1 is the worst, while 1 is the best. This value is equivalent to a Kendall's Tau correlation.

Parameters:
  • inversions (int) - Number of inversions
  • maxInversions (int) - Maximum possible inversions
Returns: float
Correlation, in [-1, 1]

maxInversions(n)

 

Maximum inversions for a permutation of a sequence of n elements Note: This will always return an integer

Parameters:
  • n (int) - Number of elements
Returns: int
Maximum number of inversions between n elements

meanOfInversions(n)

 

Mean (expected) inversions for a permutation of a sequence of n elements Note: This returns a float, as the expectation maybe fractional.

Parameters:
  • n (int) - Number of elements
Returns: float
Mean number of inversions across all permutations

rawInversionCounts(n)

 

Get the count of the number of permutations with k inversions, as a vector of Inv(n,k) in the form [Inv(n,0), Inv(n,1), ..., Inv(n,k_max)] where n is the length of the sequence and k_max is the maximum inversions Note: This implementation uses the InversionCountsCache to boost speed

Parameters:
  • n (int) - Number of elements in the sequence
Returns: list of int
List of inversion counts, where index k gives the # of permutations with k inversions

similarityByInversions(inversions, maxInversions)

 

Similarity between sequences, given the inversions and max possible A similarity of 0 is the worst, while 1 is the best.

Parameters:
  • inversions (int) - Number of inversions
  • maxInversions (int) - Maximum possible inversions
Returns: float
Similarity, in [0, 1]

varianceOfInversions(n)

 

Variance of inversions for a permutation of a sequence of n elements Note: This returns a float, as the variance maybe fractional.

Parameters:
  • n (int) - Number of elements
Returns: float
Variance of inversions across all permutations

Variables Details [hide private]

__loader__

Value:
<zipimporter object "C:\Python27\lib\site-packages\inversiontest-1.1-p\
y2.7.egg\InversionTest\">