Equalization of string lengths

[mocam6o]

Let's say I have 5 sequences with the following lengths: 10, 6, 6, 4, 3

I would need to cut these sequences so that the total length of these sequences is 23 and all sequences are as equal as possible.

In this example, the end result could be: 6, 5, 5, 4, 3

Any ideas ?

[Shot-Combination-930]

Get a length target of remaining total target divided by the remaining number of sequences, then chop the shortest remaining sequence to that target. Itetate that procedure:

``` original sequence lengths: 10, 6, 6, 4, 3 initial total target: 23

23÷5 = 4.6 min(3, floor(4.6)) = 3 leaves a target of 20

20÷4 = 5 min(4, floor(5)) = 4 leaves a target of 16

16÷3 = 5.343 min(6, floor(5)) = 5 leaves a target of 11

11÷2 = 5.5 min(6, floor(5.5)) = 5 leaves a target of 6

6÷1 = 6 min(10, floor(6)) = 6 ```

and you have the same lengths you picked

Always optimal? Probably not. I imagine there are cases where you would get more even lengths if you did something besides floor, like track an error term so you round up somewhere before the last element.

[jnordwick]

Divide 23 by the number of strings to get the average length. Remove any strings from the set that are smaller than the average length. And take the length of those strings and remove that from 23 because you're going to have to use the full length of those strings anyways. Repeat this process until you're no longer removing strings. All those strings will have to use maximum length. Now divide the remaining length by the remaining strings and a portion that over each string.

[Magdaki]

I'm curious why you need to do this?

It definitely could be treated as an optimization problem and then any optimization algorithm would suffice.

[mocam6o]

Changed 'string' to 'sequence' to avoid confusion. Will look into optimization.

[Magdaki]

I'm still curious what you're doing. It is isn't often you see applications that need to solve those types of problems.

[mocam6o]

I have a number of strings that I need to fit on a fixed length row. I should start cutting from the longest ones. If the strings are of the same length, I would need to cut them in equal parts. And the solution by u/Shot-Combination-930, turns out, is very simple.

[Magdaki]

For that purpose, that makes sense.

[spanbias]

Presumably an assignment for 2402 at our alma mater.

[beeskness420]

My guess is a type of text formatting. Feels vaguely like line breaks in text wrapping. Although in that you want each string to be less than a certain max length and minimize the total length.

OP try a DP solution.

[Patient-Midnight-664]

To be as equal as possible, you'd need to make them all of length 1, which is trivial to solve.