-1

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.

  • What you're talking about looks like Memory Management, which is a fairly broad field with lots of algorithms you can study up on. – Erik Eidt Sep 23 '16 at 15:40
  • Yes! that's what I thought but couldn't be sure which algorithms are used on finding available empty spaces. – ag0702 Sep 23 '16 at 15:41
  • I think this sort of question would be better on Computer Science.SE – Tersosauros Oct 14 '16 at 14:54
0

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.

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.