So mostly this is me brainstorming and spewing it out into a public space.
Given N items, what is the ‘most cubic’ shape you can make with it?
Rules: The result must be a rectangular column in three dimensions.
The ideal result is a cube, but that is only possible for cubic numbers (1,8,27, etc), or N-3*N-3*N-3
the middle result is a column X*X*Y,
the worst result is a column 1*1*N.
The best case and worst case are trivial. What’s the best algorithm for the middle case?
The naive answer is start at X = Floor(N-3), so a layer of the column is X2, and then if N % X2 = 0, you have an answer, and if it doesn’t, then decrement X and try again… it just feels like there should be a cleaner answer than that…
Except that leaves the possibility of a remainder.
So for example; 11 items.
The only configuration of 11 items that results in a column is 1x1x11. But if i took the cuberoot of 11, which is 2 and change, you would start at X * Y * Z = 2 * 2 * 2, add 1 to a dimension (doesnt matter which), and end up at 223, which doesnt form a column of 11 items.
Then you should to get all prime divisors of N (including 1), and group them in 3 groups by criteria: minimal average difference between sum im group and average of group sums.
Of course, if N is prime number - only variant is 1 * 1 * N.
A good thought… though i dont know that prime divisors is what i need…
one algorithm leading to another… find all the sets of 3 positive integers that multiply to N…
hmmm… need to chew this one over.
if you start from the prime divisors, and then multiply them together until you’ve got 3 left… hmm…
You try at first… (ab) * (cd) * (ef) and calculate…
…Group productions: a * b, c * d, e * f
…Average of group productions: avg = ( a * b + c * d + e * f) / 3
…Differences: d1 = |avg - a * b|, d2 = |avg - c * d|, d3 = |avg - e * f|
…Average difference: Davg = (d1 + d2 + d3) / 3
You should to calculate Davg for all possible variants of groups and to find minimal of them. Actually if production1 = production2 = production3 than Davg = 0. That means, N is cube and any production is N^-3.
there are 90 arrangements of 6 objects into 3 groups (Stirling Number of the Second Kind, {6,3} = 90).
for 1024, there are 10 objects, and 9330 combinations (I grant you that as HUMANS, we know that the numbers are all 2, and so the actual number of combinations is actually much much smaller, but a computer doesnt know that)…
It’s… doable, theoretically. But the algorithm to create the permutational sets of groupings is eluding my mind.
Again, in pure english, this is a breeze to describe. Translating it to computer logic is… a bigger step.