Disclaimer: I'm honestly not sure whether this question is best placed at Puzzling, Maths, or Programming SE, but I'm interested in the best solution, and I'm sure mods will shift the question around, if inappropriate... It is definitely something I have been puzzling over for a while now...
(Maybe I'm just having a dumb day and need some fresher brain...)
You have a sack of N identical Lego bricks, which can be built into a row of M Lego-stacks of arbitrary height.
Obviously, one extreme is a single stack of N bricks, while the other is a row of N single bricks.
Two different in-between possibilities would for example be:
You are interested in a complete, duplicate free list of all possible solutions. What is the most efficient algorithm which outputs all possible rows that exist for any given N? The order in which the individual possibilities are output is not important.
- All bricks are identical
- Stack positions in the row are of importance, that's why the above example shows two different possibilities
- All stacks are always next to each other, i.e. a 'zero-sized-stack' on either side or in between would not constitute a solution.
Using numbers to denote stack-height and position to denote stack-position, the correct output of the algorithm for N = 4 bricks would be the following eight results (in any order):
[ 1 1 1 1 ] [ 2 1 1 ] [ 1 2 1 ] [ 1 1 2 ] [ 3 1 ] [ 2 2 ] [ 1 3 ] [ 4 ]
A valid answer provides the algorithm description in pseudo-code (or real code) which gives this output for any given input N. The most efficient (correct) code gets accepted.