0

I need to show to user a table W x H of short strings.

(Update: The table content is not mutable, I can not move strings around, change them etc.)

For simplicity sake, let's say that:

  • I'm visualizing the table using HTML;
  • a string is a single word, picked by weighted (by word frequency) random from an English dictionary;
  • W and H is in the range from 5 to 10;
  • in average case there would be probably 10-15 different words at the same time;
  • and in worst case all words in the table are different (that is up to 100 different strings).

To help visualization, I need to colorize backgrounds of the table cells. Cells with the same word should be of the same color.

The question is what is a good algorithm to assign colors to strings in this case?

Additional requirements and notes:

  • I do not want to use a hardcoded table of 100 colors, that's not fun.
  • Colors should be as visually distinguishable as possible (but with 100 colors that's hard to achieve).
  • Alternatively — adjacent cell colors must be as visually distinguishable as possible (as long as they contain different words, of course). But that will complicate algorithm.
  • I would like text in each cell to be in the same color (say, black) if possible. Again, this is hard to do with 100 colors. But at the very least, the text should be as readable as possible with any background color.
  • Ideally, I would like to do everything in a single pass for simplicity sake and assign colors on the go — but this would harm the distinguishability. So, two passes, I guess.
  • In general, performance does not matter, readability and algorithm simplicity do.
Alexander Gladysh
  • 39,865
  • 32
  • 103
  • 160

1 Answers1

0

Based on the way that you framed this question I'd also assume that the position of the words in your table is not something that you can change. I only make this distinction to confirm that you couldn't do something easy and move identical terms into adjacent cells.

In regard to coloring the cells I think the most straight forward solution would be to write an algorithm that determines the color based on the character values of the cell. Credit to Chroma Hash for making this the first thing to come to mind.

Your job will be complicated by attempting to increase the differences between adjacent cells but there are also some helpful examples available. Take a look at Brian Suda's work . Depending on how much time you want to spend handling this you can get pretty deep into determining a thorough solution as I think this would be an application of the graph theory/ vertex shading problem, or the map coloring problem. If you Google map coloring problem or algorithm max color you should quickly drown in various academic approaches.

Carth
  • 2,303
  • 1
  • 17
  • 26
  • Correct, I can't move words around, table data is immutable. I've updated the question to clarify this. – Alexander Gladysh Oct 29 '11 at 19:36
  • 1
    I'm not sure if determining the color as a function from the string value is a good idea here... Unless you'd suggest a good string difference metric, this looks no better than just picking colors randomly... Maybe I'm wrong though... See also: http://stackoverflow.com/questions/495662/mapping-arbitrary-strings-to-rgb-values – Alexander Gladysh Oct 29 '11 at 19:42
  • A good point. I think the only immediate benefit is that with the possibility of repeating terms in the array you don't need to store the random determination of word/color mappings so that your choice is consistent. The algorithm would keep it consistent. – Carth Oct 29 '11 at 20:48
  • With up to 100 strings it is not a very strong benefit ;-) – Alexander Gladysh Oct 29 '11 at 20:58