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?

Answer 1

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)))
    wIndex = hIndex + 1

   return divisors[hIndex], divisors[wIndex]

Answer 2

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.

Answer 3

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.