我有任意一组乐高积木。我也有一些由 3 块乐高积木制成的人物。我想找出当前乐高积木阵列可以创建多少种图形组合。
有人给我一些参考，所以我可以解决这个问题吗？
我可以使用哪些算法？我可以使用任何理论吗？
提前感谢您提供的任何帮助。
/汉斯
编辑：这个问题在数学堆栈交换中被重新提出。
问问题
3203 次
2 回答
5
你会相信像这样的问题，或者至少是它们的一般情况，实际上仍然是开放的研究问题吗？你在这里做真正的数学研究。;)
Søren Eilers、Mikkel Abrahamsen 和 Bergfinnur Durhuus 在乐高组合计数问题上做了一些工作，即计算可以排列六块相同的 4x2 乐高积木的独特方式的数量。您或许可以查看他们的工作（包括 Java 代码）以获取灵感。
从文本的浏览来看，他们似乎以两种不同的方式解决了这个问题：
- 使用递归块定位和计数算法。
- 使用蛮力 - 尝试六块砖在空间中的所有可能位置（即使是那些砖不接触的位置。）
提示：可能的组合数量，即使是少量的积木，也是很大的。这就是让乐高变得如此有趣的原因。
于 2012-04-10T19:12:30.513 回答
1
根据您期望的计算复杂性，您可以使用动态编程。
设 x1,x2,...xk 是一个解，使得组合 1 的 x1 个副本，组合 2 的 x2 个副本 ....
F([]) = F([x1=0]+F([x1=1]...
F([x1]) = F( [x1,x2=0]) + F( [x1,x2=1])....
该解决方案的复杂度为 O(n^k)，其中 n 是砖块的数量，k 是图形的数量。
于 2012-04-10T22:24:25.490 回答