[
https://issues.apache.org/jira/browse/RNG-62?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16696586#comment-16696586
]
Alex D Herbert commented on RNG-62:
-----------------------------------
OK. I removed the getK and GetN methods.
Note:
The method used in the CombinationSampler is a partial Fisher-Yates shuffle.
This could also be applied in the permutation sampler where the sample of P(n,
k) can do the first *k* steps of a Fisher-Yates shuffle. The resulting sample
is copied from the top *k* positions of the array.
Currently the sampler shuffles the entire array and copies the bottom *k*
positions. This is a lot slower when *k* is far smaller than *n*.
I did this change in the PermutationSampler but the unit test does not
currently test permutations for {{k<n}}. Is this worth adding as an improvement
ticket?
> CombinationSampler
> ------------------
>
> Key: RNG-62
> URL: https://issues.apache.org/jira/browse/RNG-62
> Project: Commons RNG
> Issue Type: New Feature
> Reporter: Alex D Herbert
> Priority: Minor
>
> 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)
