[jira] [Comment Edited] (RNG-62) CombinationSampler

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

    [ https://issues.apache.org/jira/browse/RNG-62?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16696682#comment-16696682 ] 

Alex D Herbert edited comment on RNG-62 at 11/23/18 11:32 AM:
--------------------------------------------------------------

{quote}Can code be shared among PermutationSampler and CombinationSampler?
{quote}
Yes. Essentially they are the same. Shuffle up to *x* locations (x = k or n-k) in an array of *n* then return the top *k* or bottom *n-k*. So the only difference is how many steps to shuffle and what section of the array to return.

This could be implemented by moving most of the code to an abstract base class with the following constructor:
{code:java}
  SubsetSampler(UniformRandomProvider rng, int n, int k, boolean permutation)
{code}
The two variants then just pass the permutation flag as {{true/false}}.

I can do this in the current PR.

It would change the signature of the PermuationSampler as the {{natural(int)}} method would move. It is a static method so I am not sure how this affects binary compatibility. Code using {{PermuationSampler.natural}} would still work as the method is public and would be inherited.


was (Author: alexherbert):
{quote}Can code be shared among PermutationSampler and CombinationSampler?
{quote}
Yes. Essentially they are the same. Shuffle up to *x* locations (x = k or n-k) in an array of *n* then return the top *k* or bottom *n-k*. So the only difference is how many steps to shuffle and what section of the array to return.

This could be implemented by moving most of the code to an abstract base class with the following constructor:
{code:java}
  SubsetSampler(UniformRandomProvider rng, int n, int k, boolean permutation)
{code}
The two variants then just pass the permutation flag as \{{true/false}.

I can do this in the current PR.

It would change the signature of the PermuationSampler as the {{natural(int)}} method would move. It is a static method so I am not sure how this affects binary compatibility. Code using {{PermuationSampler.natural}} would still work as the method is public and would be inherited.

> 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)