List Shuffling

BlitzMax Forums/BlitzMax Programming/List Shuffling

gellyware

(Posted 2005) [#1]

Any thoughts on an efficient method to 'shuffle' or randomize a List collection?

i.e.
0,1,2,3,4,5,6,7,8,9

after shuffle (randomizing)
5,8,6,1,4,9,0,2,7,3

EOF	(Posted 2005) [#2]

My approach is ...

Iterate through the list. If rnd()>0.3 remove current object from list than add it to the end of the list.

Example:

' randomize a list of items in a list

Global list:TList=CreateList()

Type foodtype
	Field name$
	Field price#
	Function Add(n$,p#)
		Local f:foodtype=New foodtype
		f.name$=n$ ; f.price=p
		ListAddLast list,f
	End Function
	Function ShowList()
		Print "----------------------"
		For Local f:foodtype=EachIn list
			Print f.name$+" - "+f.price
		Next
	End Function
	Function RandList(numtimes=3)
		For Local n=1 To numtimes
			For Local f:foodtype=EachIn list
				If Rnd()>0.3
					ListRemove list,f
					ListAddLast list,f
				EndIf
			Next
		Next
	End Function
End Type

SeedRnd MilliSecs()

Local f:foodtype
f=New foodtype

f.Add "pizza",2.50
f.Add "sausage",0.75
f.Add "pie",1.53
f.Add "onion",0.21
f.Add "soup",0.97
f.Add "crisps",0.29

f.ShowList
Print "~nrandom ..."
f.RandList
f.ShowList
End

nawi	(Posted 2005) [#3]

Just loop trough the list for say 300 times, and then make 33% (or whatever) chance of adding it to last of the list.

gellyware

(Posted 2005) [#4]

JB, thanks! This helps a lot.

taxlerendiosk

(Posted 2005) [#5]

I thought the usual way to do random permutations was to go through, and swap each element with a random one between that element and the last element (inclusive). It might be easier to do it this way with lists, I dunno.

Dreamora

(Posted 2005) [#6]

For denzils idea you better make an array out of the list, randomize it and make a list out of it again.
This would be extremely fast and gives a better randomization as you can use indizes to jump around in the list (you could that with lists as well but lists always search the index from start instead of just jumping to it)