Shuffling Algorithm

[+Karl G]

I'm trying to figure out a good 8-bit shuffling algorithm. In this case, it's for a 7800Basic project, but the strategy would likely be the same regardless of language, or even 8-bit platform.

 

The classic way to randomize a finite set of objects like cards would be to generate a random number between 0 and (#items - 1), then place the chosen item into a new list. The original list would be reduced by one, a new random number is generated for the smaller range, etc, continuing until all of the items from the original list have been selected and placed in the new list.

 

The problem with this approach is that I don't know a good, easy way to generate random values for arbitrary number ranges. For powers of two it is easy, but what about generating numbers between 0-2 or 0-4, etc?

 

Does anyone have a suggestion either for a better method for shuffling items like this, or for a decent way to generate random numbers for odd number ranges like this? 

[+Karl G]

It occurs to me that I can divide 256 by each of the "odd" ranges, and make a table for each cutoff number, distributing the bias throughout the range. then I can get my random value, and iterate through the appropriate table to determine the random number for that range.

 

threerange
    85, 170

fiverange
    51, 102, 153, 204

sixrange
    42, 85, 127, 170, 213

sevenrange
    36, 73, 109, 146, 182, 219

 

[RevEng]

Yep, that's a good way for lower-ranges. It does get a little out of hand for comparisons, for larger ranges.

 

Near powers-of-two aren't bad either. You just have to throw out results that don't match and go back to the pot. Depending on how close the range is to the power-of-two, you only wind up iterating on occasion.

; return 0-2
getval
  val=rand&3 ; val is 0-3
  if val>2 then goto getval ; throw back the any 3 result

Of course, it's not a good choice for large numbers that aren't near a power-of-two.

 

We have a thread somewhere here that have combined power-of-two random routines that are quick, but not evenly distributed. Something like this...

  val=rand & 127
  val=val+(rand & 31) ; return a value between 0-158

gives a probability curve that looks like this...

 

...which might be fine for some purposes, and beneficial for other purposes.

 

(ignore the jagged line. the segments would be perfectly straight from a probability perspective)

[BydoEmpire]

I went the cheesy and probably slow (but fairly effective) route of:

for loop = 0 to 255
	a = rand%max
	b = rand%max
	temp = mydata[a]
	mydata[a] = mydata[b]
	mydata[b] = temp
next loop

I haven't really had need to do this per frame or anything, so speed hasn't been a concern.

[ZylonBane]

On 8/27/2021 at 2:35 PM, Karl G said:

The classic way to randomize a finite set of objects like cards would be to generate a random number between 0 and (#items - 1), then place the chosen item into a new list. The original list would be reduced by one, a new random number is generated for the smaller range, etc, continuing until all of the items from the original list have been selected and placed in the new list.

That would waste RAM on two lists. You want a Fisher-Yates shuffle, which can randomize a list in-place.

https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

 

[+Karl G]

1 hour ago, ZylonBane said:

That would waste RAM on two lists. You want a Fisher-Yates shuffle, which can randomize a list in-place.

https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

 

In this case, the initial list will be in ROM, and the shuffled list would go in RAM. 

 

Edit: I did end up doing in-place shuffling after copying to RAM.