CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4
  1. #1
    Join Date
    Sep 2011
    Posts
    2

    Optimal table layout (least number of rows)

    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:

    Input: A1,A2,A3,B1,B2,C1,C2
    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).

  2. #2
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: Optimal table layout (least number of rows)

    Your problem is a type of Job Shop Scheduling. It's not clear to me what you mean by "The order of groups is fixed".
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  3. #3
    Join Date
    Sep 2011
    Posts
    2

    Re: Optimal table layout (least number of rows)

    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.

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Optimal table layout (least number of rows)

    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.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured