Data "unsort" / homogeneity algorithm

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.