Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
Have you tried something like genetic search? –  David Jul 29 '11 at 0:53
3  
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 Jul 29 '11 at 1:02
3  
Examples are essential. A unit test case is critical for this kind of thing. A paragraph of text is not a test case. –  S.Lott Jul 29 '11 at 2:22
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  ExoByte Jul 30 '11 at 0:59
    
Let me know how it works. –  Jim McKeeth Jul 30 '11 at 1:08
add comment

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.

share|improve this answer
    
OK, I'll bite. I did a Google search on tkwikibrowser and got nothing. Can you link to more information? –  Jim McKeeth Jul 29 '11 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. –  user unknown Jul 29 '11 at 20:29
add comment

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.

share|improve this answer
1  
This seems like the easiest solution, but now I'm really curious how this would perform with real world data. –  TheLQ Jul 29 '11 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. –  Jim McKeeth Jul 29 '11 at 20:01
    
And there will be exact duplicates in the data. This might be an interesting place to start though. –  ExoByte Jul 29 '11 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. –  Jon Purdy Jul 29 '11 at 20:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.