# Data "unsort" / homogeneity algorithm

In an attempt to not reinvent a wheel, I'm asking if anyone has ideas on a data homogeneity algorithm. A brief example:

My data has several elements maybe like

1. Number
2. Color
3. Fruit
4. Letter

There are around a 100 of these elements in an array. The algorithm needs to sort the elements so that any 2 entries with the same number are spaced out from each other as much as possible, and the same with color, fruit, etc. It'd also be nice if I could prioritize the elements. It feels like you'd never reach 100% so you'd give it a number of passes to make, check out the result, then try more passes on it.

I wouldn't be surprised if there's something out here that just works that I don't have enough google-fu to find.

• Have you tried something like genetic search? Commented Jul 29, 2011 at 0:53
• You write like a native English speaker, so please work on the write-up a bit. Please remove the word 'like' where it does not belong and polish your sentences in general. Also, care to provide an example? I have not fully understood your question.
– Job
Commented Jul 29, 2011 at 1:02
• Examples are essential. A unit test case is critical for this kind of thing. A paragraph of text is not a test case. Commented Jul 29, 2011 at 2:22

This kind of bugged me for a while so I had to come see if it was solved. Here is my idea. From scratch, not an application of any algorithm I am aware of. This would be a rather expensive brute force algorithm, but it should be fairly effective. It is assuming you are dealing with the realtively small data set you described (100 rows of 4 columns) and are working on modern computer with sufficient ram.

Overview: We use a recursive algorithm on a sorted list to disperse similar records to their maxiumum distance within similar records. After each call all records with the same parent are at their maximum distance. The top call includes all records. So it unsorts from the inside out.

Data structures:

• `newIndexes` is an `array<integer>`. The index of the array is the existing index of the row. The value will be the new index, starts with -1
• `data` is a `array<array<string>>`. The key is the index, the inner array is a string representation of the values in one row. Doesn't need to be a string if you have some way of grouping your data. The first array element is the one with the greatest weight.

Sort `data` by order of weight. Sort it first by the column with greatest weight, within that by column with 2nd greatest weight, etc. The result is the inverse of what you want. Index sequentially.

Here is the algorythm (in psudo code).

``````        // siblingCount: On first call is the number of rows in the table,
//    on recursive calls it is the number of elements with the same parent
// index: the index of current row in `data` - starts 0
// depth: The element index - starts 0
void unsort(int siblingCount, int index, int depth)
{
int count = 1;
string hash = concatColumns(index, depth + 1);
while ((index + count < data.count) && (hash == concatColumns(index + count, depth + 1)))
{
count++;
}

if (depth < columnCount)
unsort(count, index, depth);
else if (index < data.count)
unsort(count, index + count, 0);

int spacing = siblingCount / count;

for (int i = 0; i < count; i++)
{
var offset = 0;
while ((newIndexes[index + i + offset] > -1) & (index + i + offset + 1 < newIndexes.count))
offset++;

if (newIndexes[index + i + offset] > -1) throw new Exception("Shouldn't happen.");

newIndexes[index + i + offset] = index + spacing * i;
}
}

string concatColumns(int index, int count) // returns count columns concatinated
{
// 1,1 = "1"
// 1,2 = "1, blue"
// 1,3 = "1, blue, apple"
return "1, blue, apple";
}
``````

Then apply the newIndexes to the data to be unsorted.

Thoughts on approach: Didn't test this, but the storing of the newIndexes and resolving of conflicts may be problematic since first indexes are assigned based on least significant columns, so if there are a lot of conflicts then the greater significant columns may cluster. Might try applying offset as positive first, then negative. Or possibly do so sort of insertion in a linked list instead of an array.

• Ah! I very see what you're getting at here. Sort, then segregate based on the size of the chain of sameness. If this doesn't work outright it should be pretty close. Thanks for your help and the cleanup on the question! Hopefully I'll get to try this out the next time I need to process this kind of data in Sept. Commented Jul 30, 2011 at 0:59
• Let me know how it works. Commented Jul 30, 2011 at 1:08

That reminds me of some network algorithm I have seen, keyword 'tkwikibrowser' 'TouchGraphWikiBrowser', where the elements are combined with a kind of rubber band, but are like magnets of the same pol.

I don't know what would be the mechanics, pulling in your case, but maybe 'case' is the right keyword: the elements are put into a case, and are pushed away from the border of the case, and push away each other, more so, if they have multiple attributes in common.

They start in random postions, and move in dependency of the distance to the wall, and to the distance to similar elements, and search a stable position.

The formula to push each other away could be linear or quadratic to the distance, and you could search for a good formula live, by manipulating the values.

### update:

For the attracting power, you could simply take the inverse of distracting power. So if 2 Elements share not a single attribute, this would be the maximum attraction.

• OK, I'll bite. I did a Google search on tkwikibrowser and got nothing. Can you link to more information? Commented Jul 29, 2011 at 19:39
• You're right, I'm sorry, the name wasn't TKWiki..., but TGWiki... for TouchGraph, like here, but I only found this screenshot, no working demo, where the nodes move like on rubber band. Commented Jul 29, 2011 at 20:29

Use a random shuffle, or sort by a hash of the concatenated data: a good hash gives highly dissimilar outputs for similar inputs, so entries that are similar in any dimension ought to be separated.

• This seems like the easiest solution, but now I'm really curious how this would perform with real world data. Commented Jul 29, 2011 at 10:01
• Problem with that while hash similar is dissimilar, hash of identical rows would produce the same hash and and then sort to be adjacent. Commented Jul 29, 2011 at 20:01
• And there will be exact duplicates in the data. This might be an interesting place to start though. Commented Jul 29, 2011 at 20:03
• @Jim McKeeth: Right you are. Of course, you could also concatenate an index to make otherwise identical rows distinct by a small number of bits. You might also look into Z-order curves (trivially obtained by bit interleaving), which distribute linear data spatially such that nearby data remain so. You're looking for a permutation that delivers the inverse of that. Commented Jul 29, 2011 at 20:06