Calculation of the optimal number of columns for the layout of the table - only if the width of the table and the list of rectangles

Question

I have a list of rectangles with different sizes.

rects = [100x20, 30x10, 10x10, 70x20, 40x30, 50x10]

I am trying to display a table of these rectangles. If I had a fixed number of columns, I would simply calculate the number of rows and the size of each row and column as follows:

 numCols = 4; for (i = 0; i < rects.size - 1, i++): rect = rects[i]; col = i % numCols; row = floor(i / numCols); columns[col] = max(columns[col], rect.width); rows[row] = max(rows[row], rect.height); end for; 

Now I want my table to be configured with the maximum row width. The number of columns depends on the calculation of the optimal row width at runtime.

With the list above and the maximum row with parameter 140, I expect my table to be:

 rects = [100x20, 30x10, 70x10, 10x20, 40x30, 10x10] 100x20, 30x10 70x10, 10x20 40x30, 10x10 cols = [100, 30] rows = [20, 20, 30] 

My first idea of ​​getting closer to the situation is to cache the maximum column width for each possible number of columns. Then the last record with row width = max wins.

 max[1] = [100] max[2] = [100, 30] - wins max[3] = [100, 40, 70] - 210 > 140 max[4] = [100, 30, 70, 10] max[5] = [100, 30, 70, 10, 40] max[6] = [100, 30, 70, 10, 40, 10] 

Unfortunately, I need to create a max record for every possible column number. The list may become quite large. Does anyone know an algorithm to solve this optimization problem?

Answer 1

I see only the optimization of your solution:

Assumptions:
MaxAllowedWidth - the maximum allowable sum of all width columns

• When looking for possible solutions (your last table), stop adding new columns when the total column width exceeds MaxAllowedWidth . In your example, you should stop at the third step and not try 4, 5, 6 columns, because 3 columns already take up more space that you are allowed. Please note that at this stage we only consider the first row of elements.

• Go through the number of possible columns obtained in the previous step in the reverse order. The first applicable solution will be optimal, since it will have the smallest possible number of rows.

• In step 2, you must make sure that this number of columns actually MaxAllowedWidth into your MaxAllowedWidth . In your example, you will start with a total width = 130 (100 + 30). Then, as you go through the columns, you should check if this particular column should be enlarged. If the column needs to be enlarged, check to see if the enlarged column takes up more space than you left. If he tries to solve the problem with fewer columns. These checks will allow you to exit early and skip useless iterations / operations.

The description of the question is not so clear, I didn’t have what you want until I read the comments. max row width doesn't make any sense to me, total columns width sounds better IMO.

Answer 2

To end this question, here is the resulting table layout in action. You can set the maximum width, the number of columns is calculated based on the algorithm discussed in this thread:

http://sibirjak.com/osflash/projects/as3commons-ui/layouts/showcase/#a6-dyntable

Edit:

To change the number of boxes, open a window from the taskbar at the bottom of the sample window.