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.

I have two instances where I'd like to display information in a "justified" alignment - but I don't care if the values are switched in order. One example being displaying the usernames of people online:

Anton Brother68 Commissar Dougheater Elflord Foobar Goop Hoo Iee Joo

Rearranging them we could get exactly 22 characters long on each line:

Anton Brother68 Foobar
Commissar Elflord Goop
Dougheater Hoo Iee Joo

This is kind of a knapsack, except seems like there ought to be a P solution since I don't care about perfection, and I have multiple lines.

Second instance is identical, except instead of names and character count I would be displaying random images and use their width.

share|improve this question
    
I'm doing it in PHP, though i'm just looking for the algorithm –  Mikhail Jul 7 '11 at 15:26
    
How many spaces do you want to allow between the strings? Do you want the minimum number of spaces or is any number of spaces allowed? –  rjzii Jul 7 '11 at 15:28
    
Well i'm displaying it on the web, so all spaces will become 1. –  Mikhail Jul 7 '11 at 15:37
    
Well, you're displaying it on the web, so you can use CSS to change the presentation in arbitrary ways. –  Rein Henrichs Jul 7 '11 at 17:24
1  
Ok, but what you describe is not always possible, so what are you aiming for? Lines with equal width? Fixed number of lines? Or you want just to test if it is possible to arrange those names as in your example? –  Gabriel Ščerbák Jul 10 '11 at 21:47

2 Answers 2

up vote 1 down vote accepted

Decide the number of lines, for example by taking the total length and dividing by some maximum line size. Sort the list of names by descending length. Repeatedly take the longest name off the sorted list and add it to the shortest line so far. After you have added all names to the lines, you may want to randomize the order or sort alphabetically within the lines to make it look better.

This is a very close approximation of the optimum solution.

share|improve this answer

It doesn't feel like a knapsack problem because the utlity of all words placed is 1 (correct me if I'm wrong).

Perhaps binpacking instead?

share|improve this answer
    
Utility would be the length. You just have more than one sack :) –  Mikhail Aug 16 '11 at 23:58
    
Then what is the cost? If they all have the same utility or cost, it still doesn't feel knapsack –  Jonno Aug 18 '11 at 21:05
    
cost is also the length. They don't have same utility or cost across the items because "Joe" is 3, and "Mikhail" is 7 –  Mikhail Aug 23 '11 at 14:01

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.