Resizing Columns Algorithm

Question

I have a set of columns of varying widths and I need an algorithm to re-size them for some value y which is greater than the sum of all their widths.

I would like the algorithm to prioritize equalizing the widths. So if I have a value that's absolutely huge the columns will end up with more or less the same width. If there isn't enough room for that I want the smaller cells to be given preference.

Any whiz bang ideas? I'd prefer something as simple as:

getNewWidths(NewWidth, ColumnWidths[]) returns NewColumnWidths[]

Answer 1

I would decompose that in two steps, first decide on how much of equalizing you want (between 0 and 1) and only second adapt it to the new total width.

For example as in

def get_new_widths new_total, widths
  max = widths.max
  f = how_much_equalizing(new_total) # return value between 0.0 and 1.0
  widths = widths.collect{|w| w*(1-f)+max*f}
  sum = widths.inject(0){|a,b|a+b}
  return widths.collect{|w| w/sum*new_total}
end

def how_much_equalizing new_total
  return [1.0, (new_total / 2000.0)].min
end

Answer 2

Pseudocode:

w = NewWidth
n = ColumnWidths.count
sort(ColumnWidths, ascending)
while n > 1 and ColumnWidths[n-1] > (w/n):
    w = w - ColumnWidths[n-1]
    n = n - 1
for i = 0 to n-1:
    ColumnWidths[i] = w / n

You'll need to add some code to redistribute any roundoffs from the w/n calculation, but I think this will do it.

Answer 3

Mark Ransom's answer gives the right algorithm, but in case you're having trouble figuring out what's going on there, here's an actual implementation in Python:

def getNewWidths(newWidth, columnWidths):
    # First, find out how many columns we can equalize
    # without shrinking any columns.
    w = newWidth
    n = len(columnWidths)
    sortedWidths = sorted(columnWidths)   # A sorted copy of the array.
    while sortedWidths[n - 1] * n > w:
        w -= sortedWidths[n - 1]
        n -= 1

    # We can equalize the n narrowest columns. What is their new width?
    minWidth = w // n    # integer division
    sparePixels = w % n  # integer remainder: w == minWidth*n + sparePixels

    # Now produce the new array of column widths.
    cw = columnWidths[:]   # Start with a copy of the array.
    for i in range(len(cw)):
        if cw[i] <= minWidth:
            cw[i] = minWidth
            if sparePixels > 0:
                cw[i] += 1
                sparePixels -= 1
    return cw