Shuffling an Int Array

BlitzMax Forums/BlitzMax Beginners Area/Shuffling an Int Array

Chroma

(Posted 2008) [#1]

How does this look? Basically it's shuffling an int array so you can have a weighted certain set of numbers in a random order.

Does this look ok or how would you simplify/improve it?

SeedRnd MilliSecs()

Local bonus:Int[] =  ShuffleIntArray([1,1,1,1,1,2,2,2,3,3])

For i = 0 To bonus.length-1
	Print bonus[i]
Next

End

Function ShuffleIntArray%[](array%[])
	Local intArray%[]
	For i = 0 To array.length-1
		Local r% = Rand(array.length)-1
		intArray = intArray[..intArray.length+1]
		intArray[i] = array[r]		
		array = array[..r] + array[r+1..]
	Next
	Return intArray
End Function

Paposo

(Posted 2008) [#2]

Hello.

Mmmmm. to many slices. Slices make memory fragmentation and require data movements.

Try inside bucle make 2 random index and interchange contents.
If you not need change original array make a copy previous outside bucle.

Bye,
Paposo

Chroma

(Posted 2008) [#3]

Ah ok I get what you mean. Trying again.

EDIT: Randomizing an array without using slices is eluding me atm...

Chroma

(Posted 2008) [#4]

Ok here we go. I searched for another method and this was in some vbasic helper site. It doesn't seem to be quite as random as my slice version but I'm sure it's more efficient.

Function ShuffleIntArray%[](array%[])
	Local r%, n%
	For Local i:Int = 0 To array.length-1
		r = Rand(array.length)-1
		n = array[i]
		array[i] = array[r]
		array[r] = n 
	Next
	Return array

'	Local intArray%[]
'	For i = 0 To array.length-1
'		Local r% = Rand(array.length)-1
'		intArray = intArray[..intArray.length+1]
'		intArray[i] = array[r]		
'		array = array[..r] + array[r+1..]
'	Next
'	Return intArray
End Function

Chroma

(Posted 2008) [#5]

Ok one more modification. I added in the number of times you want to shuffle the numbers.

SeedRnd MilliSecs()

Local array:Int[] = ShuffleIntArray([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20])

For i = 0 To array.length-1
	Print array[i]
Next

End

Function ShuffleIntArray%[](array%[], numShuffles%=10)
	Local i%, j%, r%, temp%
	For j = 0 To numShuffles-1
		For i = 0 To array.length-1
			r = Rand(array.length)-1
			temp = array[i]
			array[i] = array[r]
			array[r] = temp 
		Next
	Next
	Return array
End Function

Bremer

(Posted 2008) [#6]

Perhaps if you do the shuffle loop a couple of times it produces more random result.

Chroma

(Posted 2008) [#7]

I posted the numShuffle modification 20 seconds before you posted zawran lol. But yeah that's what will do the trick.

Chroma

(Posted 2008) [#8]

And here's some more array stuff that might help a beginner.

'*** Add One item to the end of an array ***
array = array[..] + [num%]

'*** Add One item to the first of an array
array = [num%] + array[..]

'*** Insert value Before index n
n=1
array = array[..n] + [value] + array[n..]

'*** Insert value After index n
n=1
array = array[..n+1] + [value] + array[n+1..]

'*** Delete First item from an array ***
array = array[1..]

'*** Delete Last item from an array ***
array = array[..array.length-1]

'*** Delete index n
n=1
array = array[..n] + array[n+1..]

Czar Flavius

(Posted 2008) [#9]

Slices make memory fragmentation

How?

WendellM

(Posted 2008) [#10]

FWIW, Chroma's approach is what I've always used: random pair-swapping.

Paposo

(Posted 2008) [#11]

Hello.
One slice allocate memory and copy data.
The memory allocated in heap need are continuous. The SO search a continuous block.
If you free any block of memory it make a hole in heap.
This holes are used in another allocations if the size requested are <= that hole.
The SO make reorganizations consuming time.
In general is more eficient not allocate and release blocks of memory if it is not needed.
Sorry is dificult for me write this in english.

Bye,
Paposo

Czar Flavius

(Posted 2008) [#12]

Does SO mean OS (operating system)? Otherwise, ok.

Paposo

(Posted 2008) [#13]

Yes. :)
SO=OS (Sistema Operativo=Operating System).

nino	(Posted 2008) [#14]

I've never had to do random int arrays but I have randomized arrays of objects e.g a shuffle a deck of cards. What I do is have a field that is used for randomizing. I set that field to a random number (like 1-1000) and then sort the objects by it.

Matt Merkulov

(Posted 2008) [#15]

This algorhytm forms new array of numbers by sequentally choosing one of remaining items of array (used ones are marked in auxillary array).

SuperStrict

Local Nums%[] = [ 1, 1, 2, 3, 5, 8, 13, 21, 34 ]
Local NewNums%[] = RandomizedArray( Nums )
PrintArray Nums
PrintArray NewNums

Function RandomizedArray%[]( Array%[] )
	Local ArrayLength% = Array.Dimensions()[ 0 ]
	Local NewArray%[ ArrayLength% ]
	Local UsedPos%[ ArrayLength% ]
	For Local N% = 0 To ArrayLength% - 1
		Local NumPos% = Rand( 1, ArrayLength% - N% )
		Local ShiftedPos% = -1
		Repeat
			ShiftedPos% :+ 1
			If Not UsedPos[ ShiftedPos% ] Then NumPos% :- 1
		Until NumPos% = 0
		NewArray[ N% ] = Array%[ ShiftedPos% ]
		UsedPos[ ShiftedPos% ] = True
	Next
	Return NewArray%
End Function

Function PrintArray( Array%[] )
	Local Text$
	For Local N% = 0 To Array.Dimensions()[ 0 ] - 1
		Text$ :+ Array%[ N% ] + ", "
	Next
	DebugLog Text$
End Function

Matt Merkulov

(Posted 2008) [#16]

Found much less resource-demanding and more convenient algo (and still more-less "clean"):

SuperStrict
SeedRnd MilliSecs()

Local Nums%[] = [ 1, 1, 2, 3, 5, 8, 13, 21, 34 ]
RandomizeArray( Nums )
PrintArray Nums

Function RandomizeArray( Array%[] )
	Local ArrayLength% = Array.Dimensions()[ 0 ]
	For Local N% = 0 To ArrayLength% - 2
		Local M% = Rand( N%, ArrayLength% - 1)
		Local Z% = Array%[ N% ]
		Array%[ N% ] = Array%[ M% ]
		Array%[ M% ] = Z%
	Next
End Function

Function PrintArray( Array%[] )
	Local Text$
	For Local N% = 0 To Array.Dimensions()[ 0 ] - 1
		Text$ :+ Array%[ N% ] + ", "
	Next
	DebugLog Text$
End Function