Finding the optimum column and row size for a table with n elements and a given range for its proportion

Question

I am looking for an optimum way to create a table from n elements so that ideally there are no empty cells, but at the same time the proportion of the table dimensions columns / rows becomes as close to 1 as possible.

Of course if n is a square number it is easy since then

cols = rows = sqrt( n );

If n is a prime number it is also clear that there will be empty cells, so my current way to handle this is:

rows = floor( sqrt(n) );
cols = ceil( n / rows  );

For all other cases my plan is to get the prime factors of n and then search all possible permutations for those whose combination has proportions closest to 1.

So my question is: is there is a better way to do this? Or is there at least a way not having to test every possible combination of the prime factors?

score 0 · Accepted Answer · answered Jul 20 '10 at 15:05

0

Instead of doing a prime factorization of n, start from the square root and find the next larger (or smaller -- makes no difference) factor. That pair of factors will the closest to the square root, and therefore the closest to a proportion of 1:1.

answered Jul 20 '10 at 15:05

Jerry Coffin

476,176
80
629
1,111

That looks like what I do if n is a prime. But within a certain proportion range it is more important to me that there are no empty cells than that the table is a square. I am not sure if this way I will always get the best possible dimensions. – Quasimondo Jul 20 '10 at 15:16
@Quasimondo: since you're finding factors of the size, you'll get zero empty cells. Since those are the factors closest to the square root, they give you the proportion closest to 1:1 without leaving empty cells. – Jerry Coffin Jul 20 '10 at 15:24
Oh I misunderstood before. Yes, now I get it. Yes that sounds like a good way. – Quasimondo Jul 20 '10 at 15:29

score 0 · Answer 2 · answered Jul 20 '10 at 15:13

Here is some pseudocode for how I've implemented something similarly:

int rowCount;
int colCount;

double tempSQR = SquareRoot(cellCount);
int maxRowCount = RoundAwayFromZero(tempSQR);

if(tempSQR == maxRowCount)
{
   rowCount = maxRowCount;
   colCount = rowCount;
}
else if(cellCount is Even)
{
   rowCount = Min(cellCount/2, maxRowCount);
   colCount = RoundAwayFromZero(cellCount/rowCount);
}
else if(cellCount> 1)
{
   rowCount = Min((cellCount+ 1)/2, maxRowCount);
   colCount = RoundAwayFromZero((cellCount+ 1)/rowCount);
}

if(rowCount * colCount < cellCount)
    rowCount++;

Finding the optimum column and row size for a table with n elements and a given range for its proportion

2 Answers2

Linked