NewsForumsCodeLogsGallerySpecsSearch

Shuffle stack.

Monkey Forums/Monkey Code/Shuffle stack.

Paul - Taiphoz(Posted 2014) [#1]
Quick simply way to shuffle a stack of objects, could just as easily be a deck of cards, list of names or numbers or anything else you care to stack.

would love to know if there is a better way to do this, but in the mean time, hope this is of use to some one.

Function ShuffleStack:Stack<pos>(_stk:Stack<pos>)
	Local tstak:Stack<pos> = New Stack<pos>
		For Local c:pos = Eachin _stk
			tstak.Insert(Int(Rnd(0,tstak.Length+1) ),c)
		Next
	Return tstak
End Function

'*****

class pos
  field x
  field y
  ...
end class



impixi(Posted 2014) [#2]
For large stacks convert the stack to an array, shuffle the array, then rebuild the stack from the array:



Run the above in "release" mode. You should see a significant time difference on HTML target at least.


Nobuyuki(Posted 2014) [#3]
You could do a Fisher-Yates shuffle in place. This would be more efficient if we had direct access to the stack's data (less function calls), but it might be even faster than impixi's method because it doesn't copy over a new array. Don't quote me on that, though!



Edit: as I suspected.... Using impixi's test on html5:



maltic(Posted 2014) [#4]
@Nobuyuki, you've made a (very slight) mistake. Good call on the algorithm, this is exactly what I would recommend too.

Global Stk:= New IntStack

Function Main()
	For Local i:Int = 0 Until 10
		Stk.Push(i)
	End If

	Shuffler<Int>.Shuffle(Stk)
		
	For Local i:Int = 0 Until Stk.Length
		Print Stk.Get(i)
	Next
End Function


Class Shuffler<T>
	Function Shuffle:Void(stk:Stack<T>)
		For Local i:Int = 1 Until stk.Length
			Local j:Int = Rnd(i)
			Local temp:T = stk.Get(j)
			stk.Set(j, stk.Get(i))
			stk.Set(i, temp)
		Next
	End Function
	
	Function Shuffle:Void(arr:T[])
		For Local i:Int = 1 Until arr.Length
			Local j:Int = Rnd(i)
			Local temp:T = arr[j]
			arr[j] = arr[i]
			arr[i] = temp
		Next		
	End Function
End Class


All I did was change "Local j:Int = Rnd(stk.Length -1)" to "Local j:Int = Rnd(i)". This is the most up-to-date version of the Fisher-Yates shuffle, straight out of my copy of "The Art of Computer Programming". It gives you a better guarantee about randomness: no item can possibly end up in the same place it started. You might also get better performance by starting the loop at index 1. Same result, 1 less iteration.


Gerry Quinn(Posted 2014) [#5]
This is my version - note that I use my own rand():Int function but you could easily modify it to use Rnd():




Paul - Taiphoz(Posted 2014) [#6]
I was thinking about this and thought you do not need to batter through the full stack you only need to run through half of it and shuffle that half into the half you have not touched.

some initial tests this does a stack of 100 things in 20ms 

Function ShuffleStack2:Stack<pos>(_stk:Stack<pos>)
	Local midpoint:Int = _stk.Length/2
		For Local c:Int = 0 To midpoint
				Local t:pos = _stk.Pop()
				_stk.Insert(Int(midpoint+Int(Rnd(0,midpoint))),t)
		Next
	Return _stk
End Function


EDIT: thinking now doing this type of half shuffle on the array method would be lightning quick.


Nobuyuki(Posted 2014) [#7]
Paul, did you look into the other methods? They're literally an order of magnitude faster than pop-and-insert.

Yes working with arrays is gonna be faster too but the problem with stacks was simply the method of how data was shuffled around. Inserts do copy operations on large portions of the stack..


Gerry Quinn(Posted 2014) [#8]
If this is still for the problem you had the other day i.e. putting 10 objects into 10 of 160 spaces, note that my shuffle algorithm allows you to just get ten random positions without shuffling the whole stack:

Local positions = New Point[ 160 ]
' Fill them
Generic< Point >.Shuffle( positions, 10 )

..gives you ten random positions in the first ten array elements, without shuffling the rest of the array.

Realistically, shuffling 160 items won't even take an eye-blink anyway, even if you were to do it every frame which is unlikely. Your 20 ms is from using insert on a stack.

Note also that you can use the same algorithm for a stack.


ordigdug(Posted 2014) [#9]
Here is my Shuffle Method:

First I set the random seed value so your shuffle will always have varied results. Then I shuffle a random number of times within ShuffleDeck method as well. NOTE: Not included is my cCard class that contains all properties of each card.

'Set random seed value based on (year+month+day+time)
	Method SetRndSeed:Int()
		Local gd:Int[]=GetDate()
		Local dt:Int 
        
                For Local id:Int = 0 Until gd.Length
			dt += gd[id]
		Next

                Seed = dt * (dt/2)		'Seed = Millisecs()
	
		Return 0
	End Method

'Shuffle card deck	(Fisher-Yates Shuffle algorithm)
	Method ShuffleDeck:Int(cardDeck:cCard[])
		
		'Shuffle deck random number of times
		For Local r:Int = 0 To Rnd(2, 10)
			
			'Shuffle deck array
			For Local i:Int = cardDeck.Length-1 To 0 Step -1
				Local index:Int = Int(Rnd (0, i))
				'-Swap cards---------------------------------Swap contents of deck[index] with deck[i] utilizing tmp-
				Local tmp:cCard = cardDeck[index]	'Place contents of cardDeck[index] into tmp
				cardDeck[index] = cardDeck[i]		'Place contents of cardDeck[i] into cardDeck[index]
				cardDeck[i] = tmp			'Place contents of tmp into cardDeck[i]
			Next
		Next
		Return 0
	End Method



Paul - Taiphoz(Posted 2014) [#10]
Love threads like this, some one posts a little code snippet of how they do something and then other people chip in their own methods, the more little bits of code that get shared around the better this place gets :)

Nice job everyone. have a star from me :)


Nobuyuki(Posted 2015) [#11]
Bringing this thread from the dead. I've been using the Insert() version of stack shuffle in my project for the last couple weeks instead of the Fisher-Yates shuffle!!!! What was I thinking?! I believe that break has turned my brain into pea soup..... Anyway, giving the thread a bit of a bump for the newbies since Monkey containers still don't have any build-in shuffles.


TeaBoy(Posted 2015) [#12]
I thought I would look up Fisher-Yates shuffle and found Richard Durstenfeld's shuffle too so I thought I would give it a bash.

I'm sure this code can be much improved so feel free to critique ;)

' ------------------------------------------
  '  Based on Durstenfeld's Shuffle Algorithm
  ' ------------------------------------------
  ' Start sequence = 12345678
  '
  ' 1) Rnd(1,8) = 6, Sequence = 1234587, Number = 6
  ' 2) Rnd(1,7) = 4, Sequence = 123758,  Number = 4
  ' 3) Rnd(1,6) = 3, Sequence = 12875,   Number = 3
  ' 4) Rnd(1,5) = 3, Sequence = 1257,    Number = 8
  ' 5) Rnd(1,4) = 1, Sequence = 725,     Number = 1
  ' 6) Rnd(1,3) = 2, Sequence = 75,      Number = 2
  ' 7) Rnd(1,2) = 1, Sequence = 5,       Number = 7
  ' 8) Rnd(1,1) = 1, Sequence = 5,       Number = 5
  '  
  ' Shuffled sequence = 64381275
  ' 
  ' Reverse sequence to conform with algorithm
  ' ------------------------------------------
Import mojo

Class shuffle Extends App

  Field numberList : Stack<Int> = New Stack<Int>
  Field newList    : Stack<Int> = New Stack<Int>
  Field getList    : String
  
  Method OnCreate()
    For Local i:= 1 To 9
      numberList.Push(i)
    Next
    
    numberList = Shuffle(numberList)
    
    For Local getTxt:=Eachin numberList.Backwards()
      getList += getTxt
    Next
    
    SetUpdateRate(60)
  End Method
  
  Method Shuffle:Stack<Int>(data : Stack<Int>)
    Local numListLength : Int
    Local lstLength     : Int
    Local rndNum        : Int
    Local getData       : Int
    Local getLast       : Int
    Local tmpList       : Stack<Int> = New Stack<Int>
    
    Seed = Rnd()*Millisecs()
    
    numListLength = data.Length()
    
    For Local n:= 0 To numListLength-1
      lstLength = data.Length()-1
      rndNum    = Rnd(0, lstLength)
      
      getData   = data.Get(rndNum)
      getLast   = data.Get(lstLength)
      
      data.Set(rndNum, getLast)
      tmpList.Push(getData)
      
      data.Remove(lstLength)
    Next
    
    Return tmpList
  End Method
  
  Method OnRender()
    Cls(0, 0, 0)
    
    DrawText("Durstenfeld Shuffle", DeviceWidth/2, (DeviceHeight/2)-50, .5, .5)
    DrawText(getList, DeviceWidth/2, DeviceHeight/2, .5, .5)
  End Method
  
  Method OnUpdate()
    If KeyHit(KEY_SPACE)
      
      numberList = Shuffle(numberList)
      
      getList = ""
      
      For Local getTxt:=Eachin numberList.Backwards()
        getList += getTxt
      Next
    End If
  End Method
  
End Class

Function Main()
  New shuffle
End Function