Fisher Yates Shuffle for cards or any number of items

Fisher Yates Shuffle for cards or any number of items - Printable Version

+- QB64 Phoenix Edition (https://staging.qb64phoenix.com)
+-- Forum: QB64 Rising (https://staging.qb64phoenix.com/forumdisplay.php?fid=1)
+--- Forum: Code and Stuff (https://staging.qb64phoenix.com/forumdisplay.php?fid=3)
+---- Forum: Utilities (https://staging.qb64phoenix.com/forumdisplay.php?fid=8)
+---- Thread: Fisher Yates Shuffle for cards or any number of items (/showthread.php?tid=1766)

Fisher Yates Shuffle for cards or any number of items - bplus - 06-19-2023

As discussed in Ranking Poker Hands:

Code: (Select All)
TopN = 52

ReDim n(1 To TopN) 'repeatable for ref

For i = 1 To TopN

    n(i) = i

Next

For i = TopN To 2 Step -1 ' Fisher Yates Shuffle of N Items

    Swap n(i), n(Int(Rnd * (i) + 1))

Next

For i = 1 To TopN

    Print "  "; i; "-"; n(i); Chr$(9);

Next

Print

At maximum you need only swap n-1 items!

RE: Fisher Yates Shuffle for cards or any number of items - PhilOfPerth - 06-20-2023

(06-19-2023, 11:19 PM)bplus Wrote: As discussed in Ranking Poker Hands:

Code: (Select All)
TopN = 52 ReDim n(1 To TopN) 'repeatable for ref For i = 1 To TopN n(i) = i Next For i = TopN To 2 Step -1 ' Fisher Yates Shuffle of N Items Swap n(i), n(Int(Rnd * (i) + 1)) Next For i = 1 To TopN Print " "; i; "-"; n(i); Chr$(9); Next Print

At maximum you need only swap n-1 items!

Is this faster than

For a = 1 To numtiles
swop = Int(Rnd * numtiles) + 1
Swap tiles(a), tiles(swop)
Next
To me, it looks the same, only in reverse order Huh

RE: Fisher Yates Shuffle for cards or any number of items - bplus - 06-20-2023

Nearly as fast but you are doing one extra swap.

But more importantly, it is less efficient, you are swapping each time with a random from whole set which can cause ripples or waves that upset a normal distribution. The wiki will confirm this but the math is quite wonky.
https://en.wikipedia.org/wiki/Fisher–Yates_shuffle see Naive method which is yours basically.

RE: Fisher Yates Shuffle for cards or any number of items - PhilOfPerth - 06-21-2023

Thanks bplus.
I thought there would be some subtle difference, but couldn't see what it was.
But I think I'll stick to the "Naive" method - it's simpler, and, for me, simplicity is of the essence.

RE: Fisher Yates Shuffle for cards or any number of items - bplus - 06-21-2023

(06-21-2023, 12:48 AM)PhilOfPerth Wrote: Thanks bplus.
I thought there would be some subtle difference, but couldn't see what it was.
But I think I'll stick to the "Naive" method - it's simpler, and, for me, simplicity is of the essence.

It's subtle and I can relate to sticking with things I understand.

Certainly we've all bigger fish to fry! Smile

Thanks for checking it out and you are not alone, Steve wasn't buying the math stuff either when I posted at the other forum. Oh well... carry on