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” 🙂
We developers, we have a tendency of organizing objects into lists, collections, queues, stacks …
Since you’ll be using the for loop to iterate over elements – why not sort the elements first. What’s more, a sorted list is easier (read: faster) to be searched upon.
For example, for a list of TDeveloper objects you would need developers (instances of TDeveloper) sorted, in the list, by their name, knowledge or salary – or any other property.
That’s boring! I want my lists randomized!
What if you need to randomize the position of elements in a list? Is there an “UnSort” method you can use? Is there a “Randomize” method in TStrings (or similar)? 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.
Unsorting by sorting 🙂
So how do you unsort a list? Well, by sorting in random order. Here goes:
var //TMyObject = class(TObject) objects : TObjectList<TMyObject>; begin objects := TObjectList<TMyObject>.Create(true); //uses System.Generics.Collections try //"missing" code! //add instances of TMyObjects to the "objects" list... //randomize / UNSORT / SHUFFLE positions objects.Sort(TComparer<TMyObject>.Construct( function(const L,R : TMyObject) : integer begin //returns -1, 0 or 1 result := -1 + Random(3); end )); //"missing" code! //do something with randomized items finally objects.Free; end; end;
That’s it. Call the Sort method by specifying a comparer that would randomly set if an element is less than or greater than the compared element.
This looks lovely, but if you have different lists of different objects that you want to have shuffled, you might want to have a more simple way to call the “unsort” code.
TGenericListHelper
Here’s a sample generic list helper class exposing class methods. There are actually 2 unsort/shuffle methods – so pick the one you prefer better 😉
TGenericListHelper = class class procedure Shuffle<T>(const listOfT : TList<T>); class procedure UnSort<T>(const listOfT : TList<T>); end;
And the implementation part:
class procedure TGenericListHelper.Shuffle<T>(const listOfT: TList<T>); //randomize positions by swapping the position of two elements randomly var randomIndex: integer; cnt: integer; begin Randomize; for cnt := 0 to -1 + listOfT.Count do begin randomIndex := Random(-cnt + listOfT.Count) ; listOfT.Exchange(cnt, cnt + randomIndex) ; end; end; class procedure TGenericListHelper.UnSort<T>(const listOfT: TList<T>); //randomize positions by unsorting begin Randomize; listOfT.Sort(TComparer<T>.Construct( function(const Left, Right : T) : integer begin result := -1 + Random(3); end )); end;
You can, of course, use the above for any list (of any specific type), like:
//"pseudo" code ... type TMyRecord = record b : boolean; i : integer; s : string; end; var intList : TList<integer>; strList : TList<string>; recList : TList<TMyRecord>; begin //add items to lists... //... //shuffle elements TGenericListHelper.Shuffle<integer>(intList); TGenericListHelper.Shuffle<string>(strList); TGenericListHelper.Shuffle<TMyRecord>(recList); end;
Shuffle me gently by a sample …
Here’s a dummy example where a list of letters is displayed in a list box (“ListBox1”), then shuffled and displayed again.
Drop a TLIstBox on a form and have it filled in the OnCreate event of the form:
procedure TMainForm.FormCreate(Sender: TObject); var c : Integer; begin for c := 65 to 90 do ListBox1.Items.Add(CHR(c)+CHR(c)+CHR(c)) ; end;
To make it more OOP (and therefore less clear to read, lol), have a class TMyObject defined as:
type TMyObject = class Value : string; end;
Now, have a TButton and handle its OnClick event to shuffle ListBox1’s elements:
procedure TMainForm.Button1Click(Sender: TObject); var objects : TObjectList<TMyObject>; myO : TMyObject; s : string; begin objects := TObjectList<TMyObject>.Create(true); try for s in ListBox1.Items do begin myO := TMyObject.Create; myO.Value := s; objects.Add(myO); end; //Option 1 objects.Sort(TComparer<TMyObject>.Construct( function(const L,R : TMyObject) : integer begin //returns -1, 0 or 1 result := -1 + Random(3); end )); //option 1 generalized TGenericListHelper.UnSort<TMyObject>(objects); //option 2 TGenericListHelper.Shuffle<TMyObject>(objects); ListBox1.Clear; for myO in objects do ListBox1.Items.Add(myO.Value) ; finally objects.Free; end; end;
If you have a simpler / shorter way to shuffle elements in lists – please do share as a comment…
As TObjectList.Sort internally uses QuickSort, I am not sure if that one will terminate when called with a random comparer. IIRC the QuickSort implementation used assumes that
IF (A < B) AND (B < C) THEN <(A
This is not guaranteed by that random comparer.
OK, that formula got scrambled by the formatting. In case this commenting system would allow me to either edit my comment or add a correction as a reply, I could write that this formula should read
if (A < B) and (B < C) then (A < C) is true
@Uwe, I’m not sure I understand what are you not sure of, but the presented UnSort method works as expected – it randomly rearranges the elements of a list.
I think Uwe is right. Quicksort (probably any sort) depends on the fact that the results of a comparison are always the same and consistent. Using a random result certainly does something, but I doubt it shuffles properly.
I’m not certain what would be “properly” in terms of shuffling, but if the (integer) list has items 1,2,3,4,5 and after calling UnSort the order is 4,2,5,3,1 and after calling again the order is 2,1,5,3,4 (and so on), that’s good enough for me.
@zarko,
The bigger strike against the Unsort method is going to be the performance characteristics. They’re going to be very uneven since the Comparer is returning random results — almost certainly worse on average than a normal quicksort. I’m still worried about the quicksort implementation getting into some very strange states with a random comparer as well.
Also, your Fisher-Yates shuffle can stop at list.Count – 2. There’s not really any shuffling of the last element that can be done. 🙂
I should have reviewed my other open tabs before commenting.
Here’s a question asking about how various sort algorithms would perform given comparators that returned random results: https://cs.stackexchange.com/q/2336
A properly implemented quicksort should be fine, other common sorting algorithms might perform slightly worse, but not degenerate significantly. Except bubble sort.
@Tony: great discussion, thanks for the link.
@Tony,
Yes, the (Fisher-Yates) Shuffle implementation can stop at -2, but -1 feels more natural even though the last step makes no sense.
As for the UnSort, again, this is just “sorting” in random order, I do not see a problem here. I have it working without any issues (on small lists though). If performance would turn to be problematic I would go for the Shuffle method. Frankly, I’m always using the Shuffle method. The UnSort is a funny way to present how one can sort by unsorting 🙂
Why not use the simple Satolo cycle to unsort?
Example code (for an array, but you’ll get the point)
uses math;
var
a:Array of cardinal;
i,j:integer;
t:cardinal;
begin
randomize;
a:=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19];
i := length(a);
while i > 0 do
begin
dec(i);
j :=randomrange(Low(a),i);
t:=a[i];a[i]:=a[j];a[j]:=t;
writeln(a[i]);
end;
end.
It is a specialization of a fisher yates shuffle. https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Sattolo's_algorithm
This method of sorting can end up in an endless loop, or take an enormous amount of time to finish. Its distribution is also not even (not quite sure why, but I did this test because I suspected as much). To test I did this
Create a grid of vertices inside a 2×2 square (around 0,0). To test how good a random sample is I see if it is inside the unit radius circle inside the square. Random sampling that counts vertices inside the circle should approximate pi = 4 * InCircle/SampleSize.
Your method has the largest deviation from pi and preforms the worst in terms of speed.
Hi jasper,
Thanks for the comments.
I guess for every job the tool to be used is not always the same.
For what I needed (shuffle a “deck of cards”) – the proposed “unsorting” works well.
-ž