Introduction
People love chaos. Many things could be ordered and sorted, but usually we don't do it. Everything that could have a non-ambiguous order can be used to encode a number, because there are Factorial(count)
enumerable permutations.
After reading this article, you'll encode messages in the order of arbitrary things. (Maybe you'll tidy up your room just for the fun of it.)
I was a little impressed by an example of storing a text message in a deck of 52 playing cards. I liked the algorithm, because it is clear and easy to implement. So I adapted it to store any stream of binary data in any Collection<IComparable>
.
The class can be used to encode things in - for example - notes, shopping lists or the palette of GIF graphics. If you like the sport of Geo Caching, you often deal with lists of GPS waypoints. The order of the waypoints in a LOC or GPX file may depend on the time you plan to visit those places, the distance to your home or just arbitrary. That means we can apply the playing cards algorithm to your waypoints file, storing a short text in the order of the locations.
This article describes the generalized C# implementation and introduces a demo application for simple word lists as well as Geo Caching files. The application can import GPX and LOC files, sort them to encode an UTF-8 text message an export the result. (If nobody really needs that, it's still a quick GPX-LOC-converter.)
Encode by Sorting
The plan is to take a collection of IComparable
and swap the objects to encode the content of a Stream
:
public static void Encode<T>(
Collection<T> source,
Collection<T> result,
Stream messageStream)
where T: class, IComparable
{
Every message is a number. We don't need to know if it is plain text, a music file or anything else, because we'll treat the whole stream as one big integer.
messageStream.Position = 0;
byte[] buffer = new byte[messageStream.Length];
messageStream.Read(buffer, 0, buffer.Length);
BigInteger message = new BigInteger(buffer);
Before we can order a list of objects, we have to define a sort key and its default order. For a list of people, the names can do the job. Geo Caches (Waypoints) can be sorted by coordinates, ID, name, distance to home, ... anyway, IComparable
objects compare themselves. We'll sort the carrier items the way they want to be sorted and define that order as "0".
T[] sortedItems = new T[source.Count];
source.CopyTo(sortedItems, 0);
Array.Sort(sortedItems);
A list in default order (i.e. alphabetical) encodes a value of "0". The first two items swapped might mean "1" and so on. One possible way to place the items of the source list in the free slots of the code list is integer division: For each item of the source list, you divide the message by the count of free slots and place the item [remainder] slots from the left. Hence we need a carrier list of the same length as the source list, and we need to know the current count of free slots in that list.
Collection<int /> freeIndexes = new Collection<int />();
result.Clear();
for (int n = 0; n < source.Count; n++)
{
freeIndexes.Add(n);
result.Add(null);
}
After these preparations, we can iterate over the source list (which is in "0"-order") and calculate each item's new position from the remaining message.
int skip = 0;
for (int indexSource = 0; indexSource < source.Count; indexSource++)
{
skip = (message % freeIndexes.Count).IntValue();
message = message / freeIndexes.Count;
int resultIndex = freeIndexes[skip];
result[resultIndex] = sortedItems[indexSource];
freeIndexes.RemoveAt(skip);
}
Here's the complete encoder method:
public static void Encode<T>(
Collection<T> source,
Collection<T> result,
Stream messageStream)
where T: class, IComparable
{
T[] sortedItems = new T[source.Count];
source.CopyTo(sortedItems, 0);
Array.Sort(sortedItems);
messageStream.Position = 0;
byte[] buffer = new byte[messageStream.Length];
messageStream.Read(buffer, 0, buffer.Length);
BigInteger message = new BigInteger(buffer);
Collection<int> freeIndexes = new Collection<int>();
result.Clear();
for (int n = 0; n < source.Count; n++)
{
freeIndexes.Add(n);
result.Add(null);
}
int skip = 0;
for (int indexSource = 0; indexSource < source.Count; indexSource++)
{
skip = (message % freeIndexes.Count).IntValue();
message = message / freeIndexes.Count;
int resultIndex = freeIndexes[skip];
result[resultIndex] = sortedItems[indexSource];
freeIndexes.RemoveAt(skip);
}
}
How many bytes can a list store? The count of possible permutations is the factorial of the list's length. Every smaller number is the number of a specific permutation, hence a valid message. That means, every message shorter than the size of Factorial(length)
- rounded off to the count of fully used bytes - is the unique number of a permutation.
public static long GetCapacity(long listLength)
{
BigInteger capacity = new BigInteger(listLength);
capacity = Factorial(capacity);
int byteCapacity = (capacity.bitCount() / 8) - 1;
return byteCapacity;
}
Decode the Order
This time we start with a carrier list in some specific order and a message of "0". For each list item, we have to find out the remainder of the integer division in the encoding process, so we can revert the divisions. How do we know how many free slots an item skipped? Well, the source list was in "0"-order, so after one item only "bigger" items could follow. That means, the count of "bigger" items to the left is exactly the skip count which is exactly the remainder of the former division.
The message was being divided by the count of free slots, resulting in a known remainder. Before that step, it had already been divided by all earlier counts of free slots. So we can multiply the skip value by (list.Count - position)
for each position that came before the current one, sum up those values for all list items - and the result will be the message number.
Here's the decoder method:
public static void Decode<T>(
Collection<T> carrier,
Stream messageStream)
where T : class, IComparable
{
T[] sortedItems = new T[carrier.Count];
carrier.CopyTo(sortedItems, 0);
Array.Sort(sortedItems);
BigInteger message = new BigInteger(0);
for (int carrierIndex = 0; carrierIndex < carrier.Count; carrierIndex++)
{
int skip = 0;
for (int countIndex = 0; countIndex < carrierIndex; countIndex++)
{
if (carrier[countIndex].CompareTo(carrier[carrierIndex]) > 0)
{
skip++;
}
}
int itemOrdinal = Array.IndexOf(sortedItems, carrier[carrierIndex])+1;
BigInteger value = new BigInteger(skip);
for (int countIndex = 1; countIndex < itemOrdinal; countIndex++)
{
value *= (carrier.Count - countIndex + 1);
}
message += value;
}
byte[] messageBytes = message.getBytes();
messageStream.Write(messageBytes, 0, messageBytes.Length);
messageStream.Position = 0;
}
Flexible Sort Keys
When you're sorting objects, a unique sort key is important: In an address book, two people can have the same name, but unique birthdays - in another address book the names may be unique, but not the birthdays. On a route of waypoints some spots can have the same latitude, but a unique timestamp - on other routes the elevation can be the only unique property.
As the best sort key depends on the given data, it should be a property of the collection. After you filled it with comparable objects, you just tell the collection which field is the comparable one.
FlexibleComparableCollection<GeoCache> source =
new FlexibleComparableCollection<GeoCache>();
foreach (ListViewItem viewItem in lstGC.Items) {
source.Add((GeoCache)viewItem.Tag);
}
source.ComparablePropertyName = GetGCSortPropertyName();
How does this work? By a little reflection! FlexibleComparableCollection
is a typesafe generic collection. When ComparablePropertyName
is set, it looks up the property in its item type and then informs each item.
public class FlexibleComparableCollection<T> : Collection<T>
where T : FlexibleComparable
{
private PropertyInfo comparableProperty;
public string ComparablePropertyName {
get {
if (this.comparableProperty != null)
return this.comparableProperty.Name;
else return string.Empty;
}
set {
this.comparableProperty = typeof(T).GetProperty(value);
foreach (FlexibleComparable item in this.Items) {
item.UpdateComparableValue(this.comparableProperty);
}
}
}
}
The items are derived from FlexibleComparable
:
public class FlexibleComparable : IComparable
{
private object comparableValue;
internal void UpdateComparableValue(PropertyInfo comparableProperty)
{
this.comparableValue = comparableProperty.GetValue(this, null);
}
public int CompareTo(object obj)
{
IComparable thisValue = this.comparableValue as IComparable;
if (thisValue == null) return -1;
IComparable otherValue;
FlexibleComparable other = obj as FlexibleComparable;
if (other == null) otherValue = other as IComparable;
else otherValue = other.comparableValue as IComparable;
if (otherValue == null) return 1;
else return thisValue.CompareTo(otherValue);
}
}
That is all you need to abuse any collection of anything as a carrier medium. You only have to pick or invent a non-ambiguous property and make sure the message fits into the list.
private void EncodeInSomething()
{
FlexibleComparableCollection<Something> source = GetList();
source.ComparablePropertyName = "ChosenField";
Stream message = TextToStream(txtMessage.Text);
Collection<Something> result = new Collection<Something>();
OrderUtility.Encode<Something>(source, result, message);
SaveList(result);
}
private void DecodeInSomething()
{
FlexibleComparableCollection<Something> carrier = GetList();
carrier.ComparablePropertyName = "ChoseField";
MemoryStream message = new MemoryStream();
OrderUtility.Decode<Something>(carrier, message);
txtMessage.Text = new StreamReader(message).ReadToEnd();
}
The Demo Application
The application lets you enter word lists and import/edit GPS data. It displays the capacity of the current list and lets you encode/decode plain text. For a better understanding, the last tab page uses the number 1..256 as the carrier list, so you can see how the order changes with the encoded text.
Conclusion
With those few lines of code we're able to define a sort key on a list of objects, encode a binary message in the list's order and decode it again. The only requirement is one unique property, but it has to be unique only for the actual list, not for the class of objects in general.
Special thanks to Chew Keong TAN for his C# BigInteger Class and Peter Jerde for explaining the basics.
History
- 1st March, 2010: Initial post