Lego brick towers

Question

^{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.

For clarification:

• 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.

Answer 1

Let $n$ be the number of bricks. Iterate from $i = 0$ to $2^{n-1}$ and write it as binary. Start your first tower with 1 brick, and as long as you encounter 0s, you add one layer. If you encounter a 1, start a new tower. Example for $n = 4$:

000 -> 4
001 -> 3 1
010 -> 2 2
011 -> 2 1 1
100 -> 1 3
101 -> 1 2 1
110 -> 1 1 2
111 -> 1 1 1 1

Here is a visualization of how an 8-bit binary number 00010110 corresponds 1-1 with a composition of $n=9$ bricks:

Answer 2

A simple $O(2^n)$ algorithm written in Python (@Glorfindel's is $O(n\cdot2^n)$):

def ordered_compositions(n):
  """
  Yield all ordered compositions of n.
  """
  if n == 1:
    yield [1]
  else:
    for composition in ordered_compositions(n - 1):
      composition[-1] += 1 # add 1
      yield composition
      composition[-1] -= 1 # remove the added 1
      composition.append(1) # other way to add 1
      yield composition
      composition.pop() # remove added 1

for composition in ordered_compositions(4):
   print(composition)

Note that this mutates compositions (towers) after yielding them (this is why $O(2^n)$ is possible), so if you want to make a list from it, you'll have to copy each composition.

This algorithm can be found by noting that each composition of $n$ is a composition of $n-1$, with a $1$ added to the end, or with $1$ added to the last number.

For example,

the compositions of 2 are:

[2]
[1, 1]

and the compositions of 3 are:

[3]       ([2 + 1])
[2, 1]    ([2] + [1])
[1, 2]    ([1, 1 + 1])
[1, 1, 1] ([1, 1] + [1])

This algorithm could also be implemented by keeping a bool array of length $n-1$ (representing appending to the list, or adding to the last element), and a int vector (the composition). The bool array would start all false, and the vector containing $n$.

Each step would go something like this (in psuedocode), until the bool array is all ones (after $2^{n-1}$ steps):

count = 0
while (bools[count])
  pop from vector // remove the 1 brick we added when bools[count] was set
  bools[count] = false
  count += 1

pop from vector
append popped + count // combine the removed bricks to one tower

process partition

bools[count]  = true // ends a tower 1 brick earlier
pop from vector
append popped - 1 // remove the 1 brick
append 1          // add it to a new tower

This would produce results like this:

000 -> 4
100 -> 31
010 -> 22
110 -> 211
001 -> 13
101 -> 121
011 -> 112
111 -> 1111

These results are the same as Glorfindel's since the algorithms are actually the same (see annotations in the code). The only difference is that mine changes each result into the next, instead of rebuilding it each time.

Answer 3

A simple backtracking approach. $\mathcal{O}(n 2^n)$. Definitely not faster than the accepted answer. Just add a more canonical approach to this type of problems.

#include <iostream>
#include <vector>

std::vector<int> solution;
std::ostream& operator<<(std::ostream& os, const std::vector<int>& v)
{
    os << "[";
    if(!v.empty())
    {
        auto iter = std::begin(v);
        os << *iter;
        ++iter;
        while(iter!=std::end(v))
        {
            os << ", " << *iter;
            ++iter;
        }
    }
    os << "]";
    return os;
}
void f(int n)
{
    if(n == 0)
    {
        std::cout << solution << std::endl;
    }else{
        // Append new item to list. Equivalent to a 1-bit
        solution.push_back(1);
        f(n-1);
        solution.pop_back(); // Backtrack
        // Increment last item in the list. Equivalent to a 0-bit.
        solution.back()++;
        f(n-1);
        solution.back()--; // Backtrack
    }
}
void solve(int N)
{
    solution.push_back(1);
    f(N-1);
}

int main() {
    int N = 4;
    solve(N);
    return 0;
}