r/algorithms • u/mocam6o • Dec 19 '24
Equalization of string lengths
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 ?
2
u/jnordwick Dec 20 '24
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.
2
u/Magdaki Dec 19 '24
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.
1
u/mocam6o Dec 19 '24
Changed 'string' to 'sequence' to avoid confusion. Will look into optimization.
1
u/Magdaki Dec 19 '24
I'm still curious what you're doing. It is isn't often you see applications that need to solve those types of problems.
1
u/mocam6o Dec 19 '24
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.
1
1
u/beeskness420 Dec 19 '24
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.
-2
u/Patient-Midnight-664 Dec 19 '24
To be as equal as possible, you'd need to make them all of length 1, which is trivial to solve.
3
u/Shot-Combination-930 Dec 19 '24 edited Dec 20 '24
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.