计算结合乐高砖的方法的数量

Question

我有一堆乐高积木。我还有一些由3块乐高积木制成的数字。我想知道我可以创建多少个数字组合，目前乐高砖块阵列。

有人给我一些参考资料，这样我就能解决这个问题了？

我可以使用哪种算法？有什么我能用的理论吗？

谢谢您能提供的任何帮助。

/Hans

编辑:这个问题是re-asked on the math stack exchange.

Answer 1

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

S ren Eilers、Mikkel Abrahamsen和Bergfinnur Durhuus在乐高组合计数问题上做了一些工作，即计算number of unique ways you can arrange six identical 4x2 lego bricks.，您可以查看他们的工作(包括Java代码)以获得灵感。

从略读课文看，他们似乎以两种不同的方式解决了这个问题：

使用递归块定位和计数algorithm.

• Using蛮力的

1. --尝试空间中六块砖块的每一种可能的定位(甚至那些砖块不接触的块)

。

提示:可能的组合数，即使是少量砖块，也是large。这就是让乐高如此有趣的原因。

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是数字数。