Find matrix dimension so as to contain numbers

Question

Suppose N is the number of elements that I want to store in a matrix. I don't know how much this matrix has to be big. I want to easily find the minimum required size for the matrix so as to make it contain the N numbers.

As a requirement, I would like the matrix to be as compact as possible, so that:

1 2 3
4 5 6
7

is preferred to:

1 2 3 4 5 6
7

Any suggestions?

Thank you.

Answer 1

You should specify your optimization criterion, that is, how much weight you give to "squareness" versus "emptiness".

As an example of such criterion, the following code minimizes emptiness subject to the number of rows and columns being greater than 1; and picks the more square-like option if there are several minimizing sizes:

mm = ceil(sqrt(N)):-1:2; %//possible numbers of rows. Reverse order. Do not consider 1
nn = ceil(N./mm); %//corresponding numbers of columns
excess = mm.*nn-N; %//number of empty cells
[val ind] = min(excess);
m = mm(ind)
n = nn(ind)

Note that mm in the code is defined in reverse order so that min will find the last minimizing value (more square-like) if there are more than one.

For example, N=113 gives the solution m=6, n=19, resulting in 1 empty cell (=6*19-113). This solution is preferred to m=57, n=2 or m=38, n=3 (which also leave give 1 empty cell) because it is more square-like.

Answer 2

From your example I would think that the 'minimum size' may mean the solution that minimizes max(size).

In this case the solution is very simple, assuming you have L elements:

In one dimension you have:

m = ceil(sqrt(L))

And in the other dimension you have:

n = ceil(L/m)

Now a matrix of size mxn or nxm will be the matrix of minimum size with (given that size) the least amount of empty elements.