1. Technology

How to Randomize / Shuffle Collections and Lists

Implementing TList.Shuffle

By

The second law of thermodynamics, in short version and when read by a programmer, states that "any collection of objects tends not to be sorted" :)

If you are like me you have objects in your Delphi applications, custom objects (more or less complex) derived from TObject. You don't? You do!

We developers, we have a tendency of organizing objects into lists, collections, queues, stacks ...

In most situations we want our lists to be sorted out. For example, for a list of TDeveloper objects you need developers (instances of TDeveloper) to be sorted in the list by their knowledge or salary - or any other property.

Since you'll be using the for loop to iterate over developers - why not sort developers first. What's more, a sorted list is easier (read: faster) to be searched upon.

Have you ever asked yourself: why there are so many sorting algorithms? Because we like to have lists sorted!

I want my lists to be randomized!

But what if you need to randomize the position of elements in a list? Is there a "UnQuickSort" or "UnBubbleSort" algorithm you can use? Is there a "Randomize" method in TStrings? No.

Imagine a deck of cards. Yes, you see it now. How funny the game would be if you would always know what cards are on top of the deck.

Shuffle me Gently

Here's one fast randomizing procedure you can use to shuffle the elements in any TList descendant class.
 //randomize position of list elements
 procedure Shuffle(list : TList) ;
 var
   randomIndex: integer;
   cnt: integer;
 begin
   Randomize;
   for cnt := 0 to -1 + list.Count do
   begin
     randomIndex := Random(-cnt + list.Count) ;
     list.Exchange(cnt, cnt + randomIndex) ;
   end;
 end;
 
Shuffle selects an item in the list randomly, and swaps its place with the one "currently" being processed.

Note: if all you are interested only in "how to shuffle list items", stop reading here!

Strong Nerves Example

Here's a dummy example where a list of letters is displayed in a list box ("ListBox1"), then shuffled and displayed again:
 //fill ListBox1
 var
   c : Integer;
 begin
   for c := 65 to 90 do ListBox1.Items.Add(CHR(c)) ;
 end;
 
Now, just to make the code harder to read, let's introduce a TMyObject class ...
 type
   TMyObject = class
     Value : string;
   end;
 
And finally, here's how to use the Shuffle procedure:
 var
   objects : TObjectList;
   myO : TMyObject;
   s : string;
   o : TObject;
   cnt : integer;
 begin
   objects := TObjectList.Create(true) ;
   try
     for s in ListBox1.Items do
     begin
       myO := TMyObject.Create;
       myO.Value := s;
 
       objects.Add(myO) ;
     end;
 
     //randomize
     Shuffle(objects) ;
 
     ListBox1.Clear;
 
     for cnt := 0 to -1 + objects.Count do ListBox1.Items.Add(TMyObject(objects[cnt]).Value) ;
 
   finally
     //"objects" own myO's
     objects.Free;
   end;
 end;
 

I've warned you. Yes, I know TStrings also has the Exchange method, and that an overloaded procedure could be used where the parameter of the Shuffle procedure is a TStrings object.

That would not be fun at all. And since programming in Delphi is fun ...

©2014 About.com. All rights reserved.