Python3实现小正方形填充大正方形的最优行列拆分方案问询

需求说明 #

• 输入：正整数列表，每个元素代表一行中小正方形的数量。例如[3,8,5,2]表示有4行，第一行3个、第二行8个、第三行5个、第四行2个小正方形，所有小正方形尺寸一致。
• 输出：嵌套列表结构，禁止出现空行，因此列数不能大于行数。原输入的单一行可以拆分为多行，示例如下：
  • 输入[3,8,5,2]，输出应为[[3], [5,3], [5], [2]]
  • 输入[14,13,2,12]，输出应为[[7,7], [7,6], [2], [7,5]]
• 优化目标：让列数尽可能多、行数尽可能少，使行列数的差值最小（无需严格为正方形，只需尽可能接近）：
  • 示例：输入[4,3,3]，输出[[3,1],[3],[3]]
  • 极端情况：输入[1,1,1]，输出[[1],[1],[1]]

现存问题 #

当输入列表元素数量较多（如200个）时，难以找到最优拆分方式。例如数字18，拆分为9+9还是6+6+6？因为拆分行会增加输出行数，进而允许更多列，形成循环/递归的矛盾问题。

现有未优化函数 #

以下函数未考虑拆分行带来的行数增加，仅以输入列表的长度作为最大列数，无法得到最优结果：

def getSquare(x):
    output = list()
    ln = len(x)
    for i in x:
        if i <= ln:
            output.append([i])
        else:
            split = list()
            nrows = i // ln
            for j in range(nrows):
                split.append(ln)
            if i % ln:
                split.append(i % ln)
            output.append(split)
    return output

print(getSquare([14, 13, 2, 12]))
# 返回结果：[[4, 4, 4, 2], [4, 4, 4, 1], [2], [4, 4, 4]]
# 对应4列，12行
# 而最优结果应为：[[7,7], [7,6], [2], [7,5]]
# 对应7列，7行（列数应尽可能接近行数，且不超过行数）

内容的提问来源于stack exchange，提问作者Amae Saeki