Shuffle nodelist

[Timbo]

Hi All,

Is there a way to shuffle an existing nodelist?

Thanks!

Tim

[Sercan Altun]

There is a swap function that changes position of two nodes. You can use that to create your shuffle function or simply modify the code and add the function yourself.

[Timbo]

Is have something like this now, but looks like that doesn't work :

var runway:CollisionRunwayNode;

var l:int = 3 + int(Math.random() * 5);

var i:int;

                        while(l--)

                       {

                               runway = runways.head;

                               runways.swap(runway, runways.tail);

                                i = 2 + int(Math.random() * 2);

                                while(i--)

                                {
                                        runway = runways.head;

                                       runways.swap(runway, runway.next);

                               }

                                runway = runways.head;

                               runways.swap(runway, runways.tail);

                       }

[Sercan Altun]

Well that algorithm kinda undos itself, let me explain

-Outer while starts with swapping head and tail
- There is a inner while loop which as a counter that will always be even number 
- - - In the inner loop you swap head with next node
- - - Since inner loop will run for even number of times it will always revert itself by changing the head back to its position
- Outer loop finishes with swaping head and tail again leaving the node list at initial condition

try implementing this
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

[Timbo]

He Sercan,

Thanks for your help! But can you please help me with implementing the Fisher Yates with the nodelist. I really don't get it with .head & .tail?

while(!nodeList.empty)

{

    // how about head / tail?

}

[Sercan Altun]

Well since we don't have length of the nodelist Fisher Yates do not work exactly but main idea is to loop over every element of an list and find another element to swap positions based on a random number;

Should be something like

var node:Node = nodelist.head; // Get first node

while( node != null) /// finish shuffle if you hit end of the list

{
var rand:int = Math.round( Math.rand() * someShiftAmount ); // We shift this amount

var switchnode:Node = node.next;

for( var i:int = 0; i<rand; i++)

{

if( switchnode.next != null )

switchnode = switchnode.next;

}else{

switchnode = nodelist.head; // Return back to head if you are at the end of the list

}

} nodelist.swap( node, switchnode ) // Make the switch

node = node.next;

}

havent tried it.. Just put it together in mail. I think this will work. You need to set someshiftamount  a value not so small to increase randomness but not too high to slow down your code. LinkedLists are not arrays so you have to iterate to reach the swapnode.

[Timbo]

Thanks Sercan!

You really helpen me, it is working now. This is the final code

private function shuffleRunways():void

{

        var node:Node = runways.head; // Get first node

       

        while(node != null) /// finish shuffle if you hit end of the list

        {

                var switchnode:Node = node.next;

               

                if(switchnode != null)

                {

                        var rand:int = int(Math.random() * 6); // We shift this amount

                       

                        for( var i:int = 0; i < rand; i++)

                        {

                                if(switchnode.next != null)

                                {

                                        switchnode = switchnode.next;

                                }else

                                {

                                        switchnode = runways.head; // Return back to head if you are at the end of the list

                                }

                        }

                       

                        runways.swap(node, switchnode) // Make the switch

                }

               

                node = node.next;

        }

}