Hacker News Reader

Comment by klingonopera | Hacker News Reader

A use case may be shuffling the entire list, if I'm not mistaken?

They specifically say that a nice thing about Vitter's algorithm is that it produces its results in sorted order, and that it's easy to shuffle them after they've been drawn.

> The reason it’s nice for an algorithm to produce results in sorted order is because it’s easy to randomize the order after the fact.

...but is it actually so? The more I think about it, the entire topic seems to be, how do you say, a dog biting its own tail?

You have a sorted list. Now randomize it. Either you pick random from source, or you place randomly into destination. And then, as k approaches n...

An easy way to randomise a list is the following:

    import random
    
    list = [0,1,2,3,4,5,6,7,8,9]
    length = len(list)
    
    for i in range(1,length):
        j = length - i 
        k = random.randrange(j+1)
        list[j], list[k] = list[k], list[j]
    
    print(list)
    [3, 9, 6, 4, 7, 8, 5, 1, 0, 2]

The randrange(j) can be done quickly by finding the smallest power of 2 above j and then picking randomly below it until you get an answer less than j.

Wouldn't this have a bias to how the initial input sequence is?

EDIT: On the other hand, due to randomness, it could cancel itself out, I don't know, beats me. My brain hurts, at this point, I'd try to figure it out statistically first, to see if it's even a valid assumption before continuing the theoretical thought, but I'm presently too lazy to code that out... it's Friday, cheers.

That code doesn't work as written (there is an off-by-one error in the first iteration of the loop). But the intended algorithm (starting at the end of the list, swap each element with a random predecessor) doesn't produce a uniform distribution anyway; for instance it will never produce an output where the last element is unchanged.

I had an error which I believe I have now fixed. The intended algorithm is "starting at the end of the list, swap each element with a random predecessor or possibly with itself".

You can shuffle k items in O(k) time using an algorithm that swaps items in place. You can't use a similar algorithm to pick k out of n because that'd require you to materialize all n items in memory simultaneously, which exceeds the space constraints.

I thought of swapping too, but there's something about it I can't quite fathom, that tells me, it will not be "truly" randomized as with the method I described above...

...and a way to offset that, if you insist on the method of swapping, would be to remember what you've swapped and cross-checking that, but then you end up with the same problem as when you pick random items...

OscarCunningham's implementation https://news.ycombinator.com/item?id=20961548 remembers what has already been swapped using the counter i.

Fisher-Yates [1] algorithm is proven to "produce an unbiased permutation: every permutation is equally likely".

Additionally, "The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place."

[1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

According to examples in the English Wikipedia, the method I described above is actually the Fisher-Yates method (and its naive implementation, and thus the O(n²) complexity), and the swapping method on everyone's minds was actually Durstenfeld's (optimization?), with O(n).

The initial code snippet intended to be Durstenfeld was erroneously an off-by-one Sattolo implementation, which then further solidifyed my suspicion that it had a bias, which Sattolo's implementation actually indeed has. The Durstenfeld method is however proven to be unbiased.

To add further confusion to the names in the issue, though some readers might not be able to verify due to the language barrier, the German Wiki states (claims?) Fisher-Yates is Durstenfeld's method with O(n), and the "naive" Fisher-Yates is labelled as the "direct" approach, with O(n²). The name Durstenfeld is not mentioned anywhere on the German Wiki. Though the names are different, the maths are the same in both English and German. I speak German and often read both versions of an article, in case anyone's wondering why I even brought up the topic.

Thank you for posting the link.

EDIT: I try not to post usernames in text, in case anyone ever changes their name.

EDIT2: I recommend to always positively increment an iterator from 0 to n-1, and use in-loop arithmetics to get the actual desired iterator/index you require. It's less performant, but I'd argue mistakes are less common.

How long do you think it will take you to shuffle a list of size 2^64?

Reply on news.ycombinator.com