algorithm - 数数乐高积木的组合方式

Question

我有任意一组乐高积木。我也有一些由 3 块乐高积木制成的人物。我想找出当前乐高积木阵列可以创建多少种图形组合。

有人给我一些参考，所以我可以解决这个问题吗？

我可以使用哪些算法？我可以使用任何理论吗？

提前感谢您提供的任何帮助。

/汉斯

---

编辑：这个问题在数学堆栈交换中被重新提出。

Answer 1

你会相信像这样的问题，或者至少是它们的一般情况，实际上仍然是开放的研究问题吗？你在这里做真正的数学研究。;)

Søren Eilers、Mikkel Abrahamsen 和 Bergfinnur Durhuus 在乐高组合计数问题上做了一些工作，即计算可以排列六块相同的 4x2 乐高积木的独特方式的数量。您或许可以查看他们的工作（包括 Java 代码）以获取灵感。

从文本的浏览来看，他们似乎以两种不同的方式解决了这个问题：

1. 使用递归块定位和计数算法。
2. 使用蛮力 - 尝试六块砖在空间中的所有可能位置（即使是那些砖不接触的位置。）

提示：可能的组合数量，即使是少量的积木，也是很大的。这就是让乐高变得如此有趣的原因。

Answer 2

根据您期望的计算复杂性，您可以使用动态编程。

设 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 是图形的数量。