Here’s a curious problem I’ve come across: There are N columns in a table of width W, with each column having content that requires a maximum width of M1, M2, M3, … , MN, where M1 + M2 + M3 + … + MN > W. Find an optimal size, O1, O2, O3, … , ON, for all columns in the table, where O1 + O2 + O3 + … + ON = W, and where for all i between 1 and N, Oi / W ≤ R, where R is an arbitrary ratio less than 1 and greater than 0. That is to say, optimally sized means each Oi / W = min(R, Mi / (M1 + M2 + M3 + … + MN)), but when the min function chooses its first argument, the extra space, ([second argument] – [first argument]) * W, needs to be proportionally distributed to the remaining Oj, where j is between 1 and N and does not equal i, and where “proportionally” means related to the proportions of Mj / (M1 + M2 + M3 + … + MN). However, proportionally distributing this excess to the remaining columns may push a remaining column’s ratio over R, which means some of that excess might further have to be redistributed.
The iterative approach to this problem is easy, but I am interested in determining a non-iterative solution to finding all of the Oi, where I simply have a formula Oi = [yada yada yada].
Here’s code for the iterative solution when applied to columns of a QTreeView, with N = 3 and R = .42, which is derived from my AutoSizingList class of ZMusicPlayer. It uses QTreeView’s sizeHintForColumn to determine Mi.
So essentially, the problem is that the do-while on lines 18 and 41 should be eliminated. It is required in the first place because when proportionally redistributing the difference between the arguments of the min function (outlined in the first paragraph), the ratios of the columns receiving this extra width may exceed R, which means another iteration must be done to readjust. Anyone have a non-iterative solution? Also, to the Qt experts out there, why is the hack required on line 49?
I am interested both in a practical Qt approach and a mathematical approach, the latter being more interesting. Doesn’t this seem like functionality that aught to already be a part of Qt?
Update: A conversation with a friend over AIM has produced a plain-English explanation in the form of a dialogue of the above problem.
Jason: on a piece of paper
Jason: making all the lines and rows
Jason: so this table happens to have 3 columns
Jason: and a bunch of rows
Jason: make sense?
Pasternak: yes
Jason: ok
Jason: now each cell of the table is supposed to have some information in it
Jason: different length information takes up more width in the table
Jason: Rob Pasternak takes up more room than Yi Chan, for example
Jason: it’s wider
Jason: it has more characters
Jason: right?
Pasternak: yes
Jason: now say that the biggest piece of data in the first column requires a width M1, the biggest in the second column requires a width M2, and in the third, M3
Jason: Rob Pasternak, Yi Chan, and Salvadora Manello Envelopa Dali
Jason: are the biggest pieces of data for each of the three columns respectively
Pasternak: ok
Jason: now let’s say you’re writing down your table on a napkin
Jason: so you can only make it a certain width
Jason: because the napkin is small
Jason: and you’re bad at writing with tiny handwriting
Pasternak: ok
Jason: so you think to yourself “well, i will just make each column have its width be in the same proportion to the tiny width of the entire table as if i had tons of room to draw the table and was able to make each column have the width equal to the column’s biggest name”
Jason: make sense?
Pasternak: ok
Pasternak: yes
Jason: so a simple equation for finding how big each column would be would just to do this
Jason: column1 = ( M1 / (M1 + M2 + M3) ) * tinyNapkinWidth
Jason: right?
Jason: and similarly for columns 2 and 3
Pasternak: yeah
Jason: ok so lets say you do that and then you notice that
Jason: Salvadora Manello Envelopa Dali is taking up way too much space on the table
Jason: so much so that the other two columns are too tiny to show any relevant information
Pasternak: but i thought you said
Pasternak: because each of those were the maximum
Pasternak: oh wait
Pasternak: i gotcha
Pasternak: cause the napkin is too small to make Chan visible at the right proportions
Jason: yeah
Jason: even though it’s all perfectly proportioned,
Pasternak: yeah
Jason: Salvadora Manello Envelopa Dali is just so big that
Jason: he makes Chan tiny
Jason: so you think to yourself
Jason: “how about i impose a maximum ratio each column may take up. I hereby declare that no column may use more than 40% of the entire width!”
Jason: so, you apply the first process of column1 = ( M1 / (M1 + M2 + M3) ) * tinyNapkinWidth etc
Jason: but then you say something like
Jason: “if column1 is greater than 40% of tinyNapkinWidth, make column1 equal to 40% of tinyNapkinWidth”
Jason: with me?
Pasternak: yes
Jason: so then what are you going to do with that excess width you cut off of column1?
Jason: it has to go somewhere
Jason: since we want to use all of the napkin width
Jason: so you distribute it to the other two columns proportionally
Jason: not half to one and half to the other, but in a proportion equal to the amount of data they contain
Jason: seem reasonable?
Pasternak: yeah but then one of them could go over 40
Jason: exactly!
Jason: that’s the problem
Jason: so then you do the process all over again
Jason: asking “does any column exceed 40%?”
Jason: over and over until it’s perfect
Jason: this is the iterative method
Jason: i want to figure out an expression of column1,2,3 that is as simple as our original one of “column1 = ( M1 / (M1 + M2 + M3) ) * tinyNapkinWidth” but that takes into consideration our 40% restriction
Jason: and doesn’t rely on iteration
Pasternak: for any number of columns i assume
Jason: yeah
Jason: right
I don’t think I understand the question, nor the code. Is it working, or am I tired? The do{….} while (b) will only executed either once (if any of the ifs are true) or forever otherwise. It also seems to me that the 3rd and 4th line if your ifs should be += rather than just =.
You seem to define three (types of constraints ) (here written for your example of three due to the limits of the medium)
O1+O2+O3=W
O1<=WR
O2<=WR
O3<=WR
O1<=M1
O2<=M2
O3<=M3
Am I right?
I’m not exactly sure on the math you give, but I think I understand the problem enough to attempt a solution.
First of all, since we’re dealing with pixels, it doesn’t really have to be _that_ precise. With that in mind, here’s a simple algorithm that needs only two passes:
remain=0;
for (i=0; i<n; i++){ //n – number of columns
t=suggestedwidth[i]/W;
if (t<R){
remain += R-t;
} else {
//optionally, remember the index i
suggestedwidth[i]=R;
}
}
remain = remain*W //convert ratio to pixels
//distribute pixels among all columns equally, or just to those who were too short, if you remembered the index above
Yes, I’m sure you could’ve thought of that yourself, but the point is that something like that is a suitable amount of approximation. And, even if it isn’t particulary fast, coding it like this would make it _immensly_ easier to add an additional column or three.
Hope that helps; I’ll stop by if I think of an actual mathematical solution!
^Err, I got a bit carried away with the variables there: t should use suggestedratio, and you’d need a “suggestedwidth[i]=t” under the “remain +=R-t” line.
Welcome to the wonderful world of linear programming. Your Problem is:
Maximize z = C1O1+…+CnOn with Ci = Mi/(M1+…+Mn)
Subject to
Oi <= Mi
O1+…+On <= W
-O1-…-On <= W
Oi <= W*R
See http://en.wikipedia.org/wiki/Simplex_algorithm
and http://en.wikipedia.org/wiki/Linear_programming for a starting point.
@Esben
Oi also must be proportional to Mi/(M1 + M2 + M3 … + MN), unless it hits the maximum R. As for your += vs =, take another look at the code. This code does its job very well, but I don’t want to rely on iteration.
@VPeric
When determining the ratio, precession does matter to a somewhat significant degree because we multiply ratios with an arbitrarily large width to determine pixels.
The problem is that when redistributing the difference between R and the real ratio, you may push the other columns over R, which means another iterative pass must be done to catch this.
@Florian
Thinking of it as a maximization problem… hmm. Thanks for the links.
Just thinking out loud, and did not look at your code.
I presume somebody has the formula for a hypersurface
O1 + O2 + O3 + … + ON = W, let’s call it X (note that it is like the L_1 norm).
Where there are N axis, and O1 is coordinate on the 1-axis.
From that you can write the formula for the normal to the surface. Given a point (M1, M2, M3, … , MN) you project from this point to the surface along the normal.
This satisfies the R condition or not. If not, you take the one with the higest value Oi/W>R, call it Oi,1. The surface Oi/W = R for all i, is a hypercube in this space, call it K, and it intersects X in a hypercircle (one dimension less). From Oi,1 you can connect to the hyperplane on this surface “under” Oi,1 via a hypercone. To distribute the excess in column with Oi,1 to the other columns, we need to move to the point on the hypercircle that increases all other values equally. The analogy in 3D would be if z value is too large, you move via a cone to a lower z value along the plane that is above the first bissectrice of the xy plane.
Still following? I cannot guarantee correctness, for that I would need a piece of paper and a pen, but my above reasoning would lead me to think that geometrically it can be done by solving some systems to find the intersection points. So just a library to solve linear system of equation would be needed, but those are very fast.
@BennyM: Projecting along the normal is the wrong thing to do here. The normal vector of that hypersurface is simply a vector of all ones. Projecting along it means removing the same k from all Oi, it’s not a proportional resize. What you actually want is the projection along the line (0,M) where 0 is the origin (vector of all zeros) and M is the vector of Mi, i.e. the intersection of that line with the hyperplane. Computing that is trivial (just multiply all the Mi by W/sum(Mi)), and in fact, the code already does that.
As for the R condition, the problem is that moving along such a line can make you run out of the hypercube in another dimension. I can’t really think of a better solution than either moving back along another line or stopping at the border of the hypercube and taking a new line (which only distributes to the dimensions which are not maxed out yet) from there (which sounds like a better / more elegant solution, but is harder to code and should give the same result in the same number of iterations, so it isn’t really that great).
While I do not quite understand why is it useful to require the “maximum” condition (I could imagine why someone might want a “minimum” condition) , the default column sizing is often very poor, it would be definitely nice if more people tried to come up with some sensible starting values.
For the kind of solution you want, the `iteration’ probably cannot be avoided (al least without the use of some complex data structures) , but something along the lines of the following (pseudo)code seems simpler and more general: all used variables are integers, the only (brief) use of floats is in the last for{} loop.
Sorry for changing your notation… your M corresponds to my CH, your O to my A. I did not change the indexes, though, so that the arrays run from 1 to n, which may not be ideal…
The same units (say, pixels) are used for A[], M[], W.
Some possibly other units can be used for CH[], T (these are used purely for dealing with proportions).
The following ought to work with a certain maximum set individually for each column. Replacing M[i]‘s with a single maximum M is possible, of course.
INPUT
Constants: n number of columns,
M[1..n] maximum allowed column widths, CH[1..n] column width hints
Variables: W total (remaining) width
OUTPUT
A[1..n] final column widths
LOCAL VARIABLES
Variables: i index in 1..n,
W total remaining width, T total hints of not-maxed-out-yet column
Invariants: W/T nondecreasing in the while{} loop,
number of maxed-out columns increasing
//Initialize … {i=1, T = sum over 1..n of CH[i], A=[0,..,0]}
…
//Find all maxed-out columns, give them the M[i] width
while(i= T*M[i])
{A[i]=M[i], W-=M[i], T-=CH[i]; i=0}
//i=0 means start over, since we found a new maxed-out column
//and hence W/T might have increased
i++;
}
//Calculate the widths of all non-maxed-out columns
for{i=1,i0) … //Fail (cannot fill W when restricted by such small maxima M[])
else … //Return A[1..n]
Use while(++i<=n) if you really really want to make the whole while statement a one-liner (initializing with i=0).
That does not change the fact that the body of while() may execute n^2 times, but this is hardly an issue for the intended application.
The body of the last loop bothers with updating W and T so that the rounding/discretizations errors (which are spread over A[]) average to zero (I hope, the sum of A[] should be the originally input W).
I have no idea what happened with the for() loop in my first posting. The second try:
//Calculate the widths of all non-maxed-out columns
for{i=1;i<=n;i++)
if (A[i] != M[i])
{A[i]=round(CH[i]*W/T), W-=A[i], T-=CH[i];}
From your chat it just looks like you need to solve a system of 3 simultaneous equations – which is easy- am I missing something here?
Maybe I’m missing something, but a quite straight-forward non-iterative algorithms can solve this. I’ve thought of two solutions, one is worst case O(n^2) and the other O(n log n).
For worst case speed of O(n^2) you calculate all widths without the additional R constraint. Then do a loop over all widths and cut all values exceeding the maximum R and calculate the sum of the cut widths. And distribute that sum of excess widths proportionally over all columns that are not equal to maximum R (or not greater than R, but of course none of them can be above R in this case). And repeat this, as long as no excess was cut. In the worst case you do that loop n times. Not more than n times, since every time either your loop stops (no excess was cut) or at least one of the widths that was not R becomes R and will stay R till the end of the iteration.
For O(n log n) you need to sort the widths according to their size. This takes O(n log n), after that the remaining part requires just O( n ). So after sorting you start from the largest width. You calculate whether it exceeds the limit R and cut it if necessary and set that to be its optimal value O (and that is also the final optimal value for that column). After that you go to a subproblem of finding the widths of the remaining n-1 columns by reducing the remaining table width by the optimal width value you found for the largest column.
Sorry I was lazy not to write some (pseudo)code… if these explanations were too ambiguous let me know, I put down some code
, given that I understood your problem correctly.
Initialize ratios for O[i] as follows
for i=1..n do {R[i]=M[i]/(M[1]+..+M[n]);mem[i]=1}
Then apply the restriction while remembering on which columns:
for i=1..n do {if R < R[i] then R[i]=R; mem[i]=0}
Finally distribute the remaining ratio Z=1-(R[1]+…+R[n]) via
for i=1..n do {if mem[i]==1 then R[i]=R[i]+M[i]/(M[1]*mem[1]+..+M[n]*mem[n])*Z}
Maybe this can be done without iteration by I think the result would be rather obfuscated. Take for example the Cramer’s rule – in it’s general form for NxN matrices it requires the determinant function.
The third iteration is of course wrong. It should be:
do
Z=1-(R[1]+…+R[n])
for i=1..n do {if mem[i]==1 then R[i]=R[i]+M[i]/(M[1]*mem[1]+..+M[n]*mem[n])*Z;
if R[i]>R then R[i]=R; mem[i]=0}
until Z ==0
This task has it’s complexity bounded below by O(n^2) because calculating the value of R[i] has impact on all the so far uncomputed values R[j].
@BennyM @Kevin
Your approaches have demonstrated the problem in a much more striking way: As pointed out by Kevin, the trouble is extending the hypercube too far in a different dimension during the redistribution. We can look at it in N-dimensions, but the burden of the R restriction still requires some clever trick.
@Tomas P
This is elegant, but as you said, it is still iterative. That’s also interesting about having a minimum instead of a maximum. Essentially they’re the same, but thinking about it as a minimum may be more effective.
@uhuu
Both algorithms you’ve mentioned are iterative as soon as you say “repeat this, as long as…”, and I basically implement them already in the post, except for the part about sorting.
@r0b0t
That looks like the start of a clever solution… One question/potential problem: after distributing the excess in the third iteration, if R[i] > R, the excess in that case only get distributed to the remaining i+1 to N columns. Is this desired? What if there was an i-x column earlier that was far below R? …or maybe this nuance is actually the essence of the solution?
my version needs <=4 loops… that’s not O(1) but at least not running an undefinable anmount of times..
double[] requestedWidths = new double[columnCount];
double totalRequested = 0;
for(int i = 0; i < columnCount; i++){
requestedWidths[i] = sizeHintForColumn(i);
totalRequested += requestedWidths[i];
}
double MAX = 0.4;
double available = 0;
double distributeTo = 0;
for(int i = 0; i < columnCount; i++){
requestedWidths[i] /= totalRequested;
if(requestedWidths[i] > MAX){
available += requestedWidths[i] – MAX;
requestedWidths[i] = MAX;
}
else{
distributeTo += requestedWidths[i];
}
}
if(available>0&&distributeTo>0){
for(int i = 0; i < columnCount; i++){
if(requestedWidths[i]
}
}
for(int i = 0; i < columnCount; i++){
m_suggestedRatio[i] = requestedWidths[i];
}
..there may be room for improvement but in my little (C#.. yes, I know) Application it works..
hrmpf….. (too aggressive “untagging”
)
http://users.informatik.haw-hamburg.de/~krohn_d/temp/columnSizing.txt
@Andreas
One question: After “requestedWidths[i] += requestedWidths[i]*available/distributeTo;”, is requestedWidths[i] guaranteed to be less than or equal to R? Or does it suffer from the same problem as the others?
Sorry, but what do you mean by iterative algorithm? Every for loop is iterative? Usually the word iterative refers to the fact that after every iteration you get little bit closer and the stopping time of the method depends on the acceptable error you set.
In that use of the iterative neither of the methods I mentioned earlier are iterative (the stopping time does not depend on the error level, given an input the number of steps is finite, regardless of error). The second approach O(n log n) I mentioned does just one loop over the widths after sorting, assigning each column its optimal value.
basically it is like this:
// M – requested widths
// O – optimal widths
// R – maximum allowed width
// tableWidth
// do sorting
// assuming that M and O are now in the order or descending values of M:
remainingWidth = tableWidth;
remainingRequested = sum(M);
// doing loop starting from the largest:
for (i=0; i<n; i++) {
O[i] = min( R*tableWidth, remainingWidth * M[i]/remainingRequested);
remainingWidth -= O[i];
remainingRequested -= M[i];
}
When you implement this just replace i with sortedM[i] inside the loop, where sortedM contains the indexes of M when it would be sorted, so you do not have to reorder the original arrays M and O in the sorting stage.
@uhuu
By iterative, I just mean running the loop an unknown amount of times until all the conditions are met. But I didn’t read your first post carefully enough; the O(n2) algorithm, which is basically the same as the one discussed in the blog post, will in fact have the redistribution loop run a maximum of n times, since a maximum of n columns can be set to R. Good thinking. I guess that redefines my problem slightly, to read “can anybody beat this efficiency”, which I think you might have done with your sorting O(n log n) solution, which is genius. I still need to think your solution through carefully.
What I would really like to know, however, is if anyone can come up with a simple expression for Oi that only uses the 4 basic operations, and maybe the min function.
Good work though, uhuu, I think your sorting-based algorithm is the most efficient one yet.
Yes, for large n, sorting first would be better, but to do that (efficiently) pretty much needs what I call a more complicated datastructure. If you can accept the increase of the code size enabling you to use sorting, that uhuu’s code is the way to go.
Sorting according to the ratios CH[i]/M[i] (ratios of hints to maxima) from largest to smallest would be needed for this to work in the case maximum sizes M[i] are set differently for each column.
There usually aren’t “formulas” (formulas that would be helpful for any programming) that would do what a (pretty much) one-line loop of uhuu does!
@Jason:
I wasn’t able to find a combination of widths, which results in any suggested ratio becoming greater than R (or MAX)… the problem with my algorithm is a bad behavior with very few columns (i.e. tables with 1 column..)