Randomly generate set of size M from array of size N 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) &lt;= 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)\$.
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) &lt; m I would expect an exception, and since that isn't the case I think there should be a comment to document the behaviour.