Home > Uncategorized > Domino sort in C#

Domino sort in C#

Image A domino sort is a term I coined to provide a way to order a list of objects that should be joined end-to-end, where the input array is out-of-order.  For Example, if an input array was “A-B”,”C-D”,”B-C” then the output array would be “A-B”,”B-C”,”C-D”. Where common letters are joined together.

I’ve used generics so that this function can be used for any type of object. The only limit is that the “top” and “tail” must be in some way mutable into a string.  

The function may throw an exception if the input array cannot be joined end-to-end. It does not do a best-match type connection, nor does it provide options if there are more than one way for the list to be ordered end-to-end.

/// <summary>
/// Recursively orders a list by linking a top and tail together
/// </summary>
/// <typeparam name=”T”>The type of the object</typeparam>
/// <param name=”orderedList”>The ordered list.</param>
/// <param name=”unOrderedList”>The unordered list.</param>
/// <param name=”top”>Function to create a string that represents the top of the object .</param>
/// <param name=”tail”>Function to create a string that represents the tail of the object</param>
private static void DominoJoin<T>(ref List<T> orderedList,
ref List<T> unOrderedList,
Func<T, string> top,
Func<T, string> tail)
{
var matched = new List<T>();
foreach (var unOrderedItem in unOrderedList)
{
var positionInList = 0; // Default to start
bool hasMatched = true; // Default to matched end-to-end
for (var i = 0; i < orderedList.Count; i++)
{
var strTop = top(orderedList[i]);
var strTail = tail(unOrderedItem);
if (strTop == strTail)
{
positionInList = i + 1;
break;
}
strTop = top(unOrderedItem);
strTail = tail(orderedList[i]);
if (strTop == strTail)
{
positionInList = i;
break;
}
if (i == orderedList.Count – 1)
{
hasMatched = false;
}
}
if (hasMatched)
{
orderedList.Insert(positionInList, unOrderedItem);
matched.Add(unOrderedItem);
}
}
// remove matches from unorderd list
foreach (var match in matched)
{
unOrderedList.Remove(match);
}
if (!unOrderedList.Any())
{
return; // All flights matched
}
if (!matched.Any())
{
// This exception is thrown when the list cannot be linked top to tail
throw new Exception(“Stack Overflow warning!”);
}
// Recurse until all flights matched
DominoJoin(ref orderedList, ref unOrderedList, top, tail);
}

I hope this helps someone! 🙂

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: