0

I'm aware of the established array-shuffling algorithms, such as Knuth-Fisher-Yates. I'm interested in proving (or disproving) that my self-made shuffling algorithm is broken. It seems to be the reverse of KFY and requires the same number of random numbers. Here's the algorithm:

for i from 0 upto n-1 do: j = random integer such as that i ≤ j ≤ n-1; exchange a[j] and a[i];

Extra: If this algorithm is indeed the reverse of KFY and working, are there any general properties, something like "the reverse of a random shuffling algorithm is also random shuffling"?

GingerBadger
  • 405
  • 3
  • 7
  • 1
    This *is* KFY. You quote, almost *verbatim*, the account given at https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm. The sole difference is that you can stop when $i==n-2$ because when $i==n-1$ you will invariably interchange the last element with itself, which accomplishes nothing. – whuber Oct 03 '17 at 13:23
  • @user5226582 I don't see at all how this is a duplicate, since the algorithm in question is completely different! – GingerBadger Oct 03 '17 at 13:48
  • @whuber I don't understand why this is KFY, since my interval for the random number j is different. Could you please explain why the interval doesn't matter in this case? – GingerBadger Oct 03 '17 at 13:54
  • 1
    Your interval for $j$ is *identical* to the one in the Wikipedia article, which is (I am cutting and pasting here) "i ≤ j < n". – whuber Oct 03 '17 at 14:06
  • @whuber Ooops, sorry! – GingerBadger Oct 03 '17 at 14:18

0 Answers0