How to fit k-length arrays to number of bigger arrays?

Question

I have n number of one-dimensional arrays similar to:

[0,0,0,0,0,1,1,1,0,0,1,1,...]

0's and 1's indicating occupation.

And k number of smaller arrays similar to:

[2,2,2], [2,2], [2], [2,2,2,2]

with varying sizes. What I want to do is to see where and how I can fit the smaller (second) arrays to bigger arrays following each other buy indexes. Example:

Domain Arrays:
[0000111001]
[0011011001]
[0011100001]
[0000100001]

Smaller Arrays:
[22]
[2]
[222]

Result:

[0020111001]
[2211011001]
[0012220001]
[0000100001]

or

[0000111001]
[0011011001]
[0012200001]
[0020122201]

I hope I could put it into words well.

My solution is:

Finding empty spots that can fit any of the smaller arrays. And creating a tree with possible combinations like;

1-First small array goes to second big arrays 3rd index and occupies 3 spaces 2-Second small array goes to first big arrays 7th index and occupies 4 spaces

etc.

and I get the patterns of every branch on the tree with depth of smaller array count. But it of course works slowly. Which algorithms can I use to solve this problem? Thank you in advance.

Answer 1

This is a bin packing problem.

The fact that you have multiple domain arrays instead of one adds trivial complexity. It's the same problem if you concatenate every domain array into one array and separate them with -1 (or any other unused value).

You can take this as a memory management problem but that adds an additional requirement of caring about fragmenting. That is, making it harder to do more packing later. This requirement was not stated in the question. Don't make this harder than it needs to be.