1

I found out the knuth shuffle was done from the end to the beginning, such as 

from random import randrange

def knuth_shuffle(x):
    for i in range(len(x)-1, 0, -1):
        j = randrange(i + 1)
        x[i], x[j] = x[j], x[i]
    return x

However, I was thinking about why we cannot use it from the beginning to the end. Like this:

from random import randrange

def knuth_shuffle(x):
    for i in range(0, len(x), 1):
        j = randrange(i, len(x))
        x[i], x[j] = x[j], x[i]
    return x

I found out the running time of the second function was always longer than the first one. Anybody has some clues of this?

Pei Li
  • 302
  • 3
  • 15
  • What is the actual difference in execution time? – tstanisl Jul 14 '19 at 20:38
  • Note the second function does one more iteration than the first one. It should be range(0, len(x)-1, 1). Does it solve the problem? – tstanisl Jul 14 '19 at 20:45
  • Note: The second implementation is actually broken and does not produce a random shuffle. Always exchange from 0 to i and never between 0 and len(array). See more here: https://stackoverflow.com/questions/5131341/what-distribution-do-you-get-from-this-broken-random-shuffle – M8RTAL Aug 06 '20 at 09:44

1 Answers1

0

Your alternative solution looks perfectly OK. It does the same, but from left to right. I've tried it (on lists up to 1 000 000 elements), and I haven't noticed any significant difference in running time. How big lists do you shuffle? What are the differences in running time? Do they depend on the size of lists?

kubica
  • 54
  • 3