[jira] [Created] (RNG-62) CombinationSampler

["Alex D Herbert (JIRA)" <ji...@apache.org>]

Alex D Herbert created RNG-62:
---------------------------------

             Summary: CombinationSampler
                 Key: RNG-62
                 URL: https://issues.apache.org/jira/browse/RNG-62
             Project: Commons RNG
          Issue Type: New Feature
            Reporter: Alex D Herbert


The sampling module contains a PermutationSampler. There is scope to create a CombinationSampler too.

[https://en.wikipedia.org/wiki/Permutation]

[https://en.wikipedia.org/wiki/Combination]

If the order of the returned sample is not important then a combination can be generated faster than a permutation. 

The sample can be optimised by only performing the first k or (n-k) steps from a full Fisher-Yates shuffle from the end of the domain to the start. The upper positions will then contain a random permutation sample from the domain. The lower half is then by definition also a random sample (just not in a random order). The sample is then picked using the upper or lower half depending which makes the number of steps smaller.



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)