Count the number of ways to combine LEGO bricks [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

I have an arbitrary array of lego bricks. I also have some figures made of 3 lego bricks. I want to find out how many combinations of figures I can create of the current array of lego bricks.

Anybody have some references for me, so I can solve this problem?

Which algorithms can I use? Any theory I can use?

Thank you in advance for any help you can provide.

/Hans

---

Edit: This question was re-asked on the math stack exchange.

Answer 1

Would you believe that problems like this, or at least their general cases, are actually still open research questions? You're doing real mathematical research here. ;)

Søren Eilers, Mikkel Abrahamsen, and Bergfinnur Durhuus did some work on a LEGO-combination counting problem, namely counting the number of unique ways you can arrange six identical 4x2 lego bricks. You may be able to look at their work (includes Java code) for inspiration.

From a skim over the text, it appears they solved the problem two separate ways:

1. Using a recursive block-positioning and counting algorithm.
2. Using brute force - trying every possible positioning of the six bricks in space (even those for which the bricks don't touch.)

Hint: The number of possible combinations, even for small numbers of bricks, is large. This is what makes LEGO so fun.

Answer 2

Depending on the computational complexity you are expecting you can use dynamic programming.

Let x1,x2,...xk be a solution such that x1 copies of combination 1, x2 copies of combination 2 ....

F([]) = F([x1=0]+F([x1=1]...

F([x1]) = F( [x1,x2=0]) + F( [x1,x2=1])....

The complexity of this solution is O(n^k) where n is the number of bricks and k is the number of figures.