String manipulation algorithm

Question

I read in an array of strings such as: aaa bb ccccc ddd eeee fffffff ggggggg. I need help working on an algorithm to fit these strings on as little lines as possible, with the maxium ammount of charcters on a line being a fixed value, for example 15. If adding another string to that line exceeds this value, I need to make a new line.

I thought searching through, finding the largest string, then concatenating with the smallest, then the concatenating that with next largest ... and so on would work, but it doesnt achieve the results I expected, any other ideas?

The output I need would look like:

aaa bb ddd eeee fffffff ggggggg

As each line has 15 charcters on it, and this is the smallest ammount of lines you could possibly have.

I'm using C sharp.

Can you explain this better? What language are you working in? What form of output do you want? — john_science
– john_science, Commented Mar 27, 2012 at 3:03
DFS would be your starting point. en.wikipedia.org/wiki/Depth-first_search — hkf
– hkf, Commented Mar 27, 2012 at 3:03
Thanks I'll have a read, I need to output the strings onto lines, with the maxium ammount of charcters on the line being 15. I'm using a list for the lines, I just need to work out how to get as many strings on a line as possible, on as little lines as possible. — rx432
– rx432, Commented Mar 27, 2012 at 3:06

Megalodon · Accepted Answer · 2012-03-27 03:15:40Z

I think what you are doing is a semi-greedy algorithm, which in this case would not give you an optimal solution. The optimal solution can be found using something like dynamic programming with memoization. I would refer you to the examples in the wikipedia article on dynamic programming. But to give you a general idea, you want to do the following:

Start filling a line with chunck of characters ( of any size) once you cannot fit a new word, check if adding the left-out word, 'instead' of one of the words in the line would give you a better fill quote. if so replace, if not leave that word out, try a new one. ( by new one I mean different size, I assume you hash all words of similar size into same buckets) once you have tried all sizes you can move on to the next line, and do the same, however, you need to also check if swapping elements between first and second lines would give you a better "total" result. Implementing this can be done in n^2, but is a bit trickier, if you don't care much about the computational efficiency, just do this brute force.

Collectives™ on Stack Overflow

String manipulation algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related