1
\$\begingroup\$

The following algorithm attempts to randomly generate a set of size M from an array of size N. It is not based on Knuth Fisher Yates shuffle, but could someone verify its correctness?

import random

def random_m(arr, m):
    if len(arr) <= m:
        return arr

    for i in range(m):
        rand = random.randint(i, len(arr)-1)
        arr[i], arr[rand] = arr[rand], arr[i]

    return arr[:m]

if __name__ == "__main__":
    print random_m([1,2,3,4,5,6,7], 5)

The above runs in\$\ O(m)\$ where as the method based on Knuth Fisher Yates runs in \$\ O(n)\$.

\$\endgroup\$
5
\$\begingroup\$

Your understanding of Fisher-Yates is incorrect: this is precisely Fisher-Yates. It merely differs from some implementations in accumulating at the start of the array rather than the end. As such the main part of the body is correct (and uniform, modulo artefacts of the RNG).

The alternative way round, accumulating at the end, would be

    for i in range(m):
        j = len(arr)-1-i
        rand = random.randint(0, j)
        arr[j], arr[rand] = arr[rand], arr[j]

    return arr[-m:]

However, I find the special case a bit confusing. if len(arr) < m I would expect an exception, and since that isn't the case I think there should be a comment to document the behaviour.

\$\endgroup\$
4
\$\begingroup\$

The code in the post is destructive — it modifies the input list arr. This approach has a couple of problems:

  1. This behaviour is likely to be surprising to the caller, since it's not documented, and since similar functions like the built-in random.sample leave their argument unchanged, and so will lead to annoyance and maybe bugs.

  2. Even once the caller understands that random_m modifies the input data, it's not likely that they will be prepared to let it do so. In most cases I expect that the caller will need to preserve their data, and so when calling random_m they will have to take their own copy:

    sample = random_m(list(my_data), m)
    

    So although random_m appears to run in \$O(m)\$, this is hiding an extra \$O(n)\$ because of the need for the caller to copy the input.

I recommend taking a look at the implementation of random.sample. This has a hybrid approach: when \$m\$ is small compared to \$n\$ it uses "selection tracking" (maintaining a set of indices of items added the sample), but when \$m\$ is large it copies the input and then uses "pool tracking" (the algorithm in the post).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.