9
$\begingroup$

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.

enter image description here

Obviously, one extreme is a single stack of N bricks, while the other is a row of N single bricks.

enter image description here

Two different in-between possibilities would for example be:

enter image description here

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.

$\endgroup$
  • $\begingroup$ Clarification: By efficient I mean computationally efficient and not shortest possible source code. $\endgroup$ – BmyGuest Apr 5 '18 at 17:28
  • $\begingroup$ Not exactly what you are looking for, but you could use the concept of a partition $\endgroup$ – Just a browsing guest Apr 5 '18 at 20:45
  • $\begingroup$ Use the Mathematica function "IntegerPartitions" $\endgroup$ – John Apr 5 '18 at 21:06
  • 1
    $\begingroup$ @Justabrowsingguest These are not partitions, they're compositions. $\endgroup$ – ffao Apr 5 '18 at 21:12
  • 2
    $\begingroup$ There's very little to optimize if you want to actually output each possibility; counting possibilities has a lot more room for optimization beyond brute force. $\endgroup$ – user2357112 Apr 5 '18 at 21:41
14
$\begingroup$

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:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ This is very neat. I'll need to verify and implement (not today anymore though), but I like what I'm seeing. Do you know a nice "programmer's" trick to perform the binary to "list" transformation efficiently as well? C++ code or similar. I'm just naivly going for a real looped check, but my gut-instincts tells me, there might be something better out there... $\endgroup$ – BmyGuest Apr 5 '18 at 18:37
  • 1
    $\begingroup$ @BmyGuest this can get as complicated as you want it to be (search for "count trailing zeros"), but there's not really a "simple" way, unless you count using builtin functions (in gcc, this would be __builtin_ctz). $\endgroup$ – ffao Apr 5 '18 at 19:10
  • 2
    $\begingroup$ Here is a simple way to see why this works. Suppose you stick the pieces together in one pile, but lay it on its side. At any seam between two bricks you can split it, or keep it as is, and in doing so you can split it in any size parts as you want. Once you are done, you tilt the parts vertical without changing their order to get a pile arrangement. Any valid arrangement is possible, and each can be created in only one way via this method. The number of ways of doing it is therefore equal to the number of choices for breaking at the seams - a factor of $2$ per seam, i.e. $2^{N-1}$ in total. $\endgroup$ – Jaap Scherphuis Apr 6 '18 at 13:46
  • $\begingroup$ @JaapScherphuis Nice illustration. $\endgroup$ – BmyGuest Apr 6 '18 at 14:01
  • $\begingroup$ @JaapScherphuis thanks for the illustration and the edit on my visual interpretation of it. $\endgroup$ – Glorfindel Apr 7 '18 at 8:02
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Any practical use of this list is probably going to be O(n * 2^n) anyway, but this is an interesting optimization so you get +1 from me $\endgroup$ – ffao Apr 5 '18 at 19:11
  • $\begingroup$ Even the print loop in the answer is already O(n * 2^n). $\endgroup$ – user2357112 Apr 5 '18 at 21:40
  • $\begingroup$ @user2357112 True, but the generation isn't. $\endgroup$ – internet_user Apr 5 '18 at 21:48
0
$\begingroup$

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;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.