How to maximize grid dimensions given the number of elements

Question

I have n elements as a input and a function make_grid(n) which will calculate the dimensions of a grid that will contain the elements. Let's suppose that n = 12, then the function must calculate that the width is 4 and the height is 3 and not 1 and 12 or so. Similarly, n = 24 should return 6 and 4.

I tried to use ceil(sqrt(n)) to get one dimension, but is not a general case at all, and playing with cases (n even, sqrt(n) == ceil(sqrt(n))) hasn't worked.

Edit: Finding the optimum column and row size for a table with n elements and a given range for its proportion I already see this question but the coding throws me for n = 24 dimensions 5 and 5. Any help?

score 1 · Answer 1 · answered Jun 03 '13 at 23:41

1

You're looking for numbers that divide n evenly, so you'll need to compute the factors of n, and take the two that are closest to sqrt(n). One will be the largest factor less than or equal to sqrt(n) (call this f) and the other will be n/f.

However, you'll get strange-looking grids for many numbers, like 74, or any prime number.

answered Jun 03 '13 at 23:41

John

15,990
10
70
110

Indeed, you are right. The cases where are numbers which factors are far between them the table will be too long or tall. I will use numbers that stay in some screen-like ratio, so that's not a problem. However I will think in the factors and `srqt(n)` idea. – Alejandro Sazo Jun 03 '13 at 23:44
Let's say n = 50, and floor(qrt(50)) = 7, but 7 is not a factor D: – Alejandro Sazo Jun 04 '13 at 00:02
You're right. It's not. That wasn't what I was suggesting, though. The factors of 50 are 1, 2, 5, 10, 25, and 50. So the two closest factors to `sqrt(50)` are 5 and 10, giving you a 5 x 10 or a 10 x 5 grid. – John Jun 04 '13 at 00:31
OK I see your point, I have to read well an answer before ask anything. Thanks for your patience, I got the idea of your solution. – Alejandro Sazo Jun 04 '13 at 02:29
I don't know if is well said in english but what I am really looking at are not the "factors" of `n`, I'm looking at the divisors of `n` – Alejandro Sazo Jun 04 '13 at 03:11

score 1 · Answer 2 · edited May 23 '17 at 11:54

1

You are looking for integer factorization algorithms.

Check here: Efficiently finding all divisors of a number

And here: http://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms

Then just choose a pair of factors that best matches your goals.

edited May 23 '17 at 11:54

Community

1
1

answered Jun 03 '13 at 23:42

paddy

60,864
6
61
103

score 0 · Accepted Answer · edited Jun 02 '22 at 12:26

The approach is as follows:

Take the integer n as the input of the function. The goal is to obtain the "squarest" table. As @John suggested we must calculate sqrt(n) to get an idea of the dimensions. On the other hand we must calculate all the divisors of n in order to do choose the nearest divisors to sqrt(n).

How do we choose the nearest low value? we can use this tip (Python): Finding index of an item closest to the value in a list that's not entirely sorted and get the index of the nearest value in the list of divisors, let's say hIndex. Then the other dimension can be calculated dividing n by divisors[hIndex] or using a new index wIndex = hIndex + 1 and get divisors[wIndex].

The Python code is this (note that I used al lazy evaluation to find the divisors):

import numbers
from math import sqrt

def get_dimensions(n):
    tempSqrt = sqrt(n)
    divisors = []
    currentDiv = 1
    for currentDiv in range(n):
        if n % float(currentDiv + 1) == 0:
         divisors.append(currentDiv+1)
    #print divisors this is to ensure that we're choosing well
    hIndex = min(range(len(divisors)), key=lambda i: abs(divisors[i]-sqrt(n)))
    
    if divisors[hIndex]*divisors[hIndex] == n:
        return divisors[hIndex], divisors[hIndex]
    else:
        wIndex = hIndex + 1
        return divisors[hIndex], divisors[wIndex]

How to maximize grid dimensions given the number of elements

3 Answers3