I'm looking for an algorithm (preferably not a heuristic algorithm) that outputs a table layout with the least possible amount of rows given a fixed number of columns. The contents of the cells are grouped and a group may not split across multiple columns. Furthermore, groups within a column are separated by empty cells (no empty cells at the top and bottom of a column are required). The order of groups is fixed. Consider the following example:
Desired amount of columns is 2.
Output: Column 1 = A1,A2,A3,empty,empty; Column2 = B1,B2,empty,C1,C2
The number of rows in this table is 5.
Note that another possible layout (group B below group A) would give a table of 6 rows and is therefore not optimal. I wonder if this problem can be mapped onto an existing well known problem (and solution).
Thanks for your reply D_Drmmr. What I mean by "The order of groups is fixed" is that the sequence of the input must be preserved. In my example it means that if you place the columns from left to right below each other, it would result in the original input. I.e. shuffling of groups is not allowed (and also cells within groups must stay in sequence).
I do not see how this is a Job Shop Scheduling problem.
Given the number of sequence items S and the wanted number of colums C you can easily calculate the minimal number of rows possible (without any space padding). It's R = S/C rounded up. Furthermore since no group may be split, R may not be smaller then the number of items in the largest group. So the lower limit for R is the largest of these two numbers.
Now since the group order is fixed it's just to layout the sequence in the densest possible way in an R by C matrix. If it doesn't fit you increase R by one and try again. Repeat until the sequence fits.
Is there an upper limit for R? Yes when you fit the whole sequence in just one column including the space padding. Any further increase of R beyond that is futile. Since you have both a lower and an upper bound for R you can find the optimal R by the way of a binary search (as an alternative to incrementing R). This will work because when R is smaller than optimum the sequence won't fit in any R by C matrix but when R is at optimum and larger the sequence will fit in every R by C matrix. The binary search is used to locate this phase transition that takes place at the optimal R.
Last edited by nuzzle; September 19th, 2011 at 02:42 PM.