I need a box-filling algorithm for a particular set of constraints.

Benjamin Hall

So I have the following setup. I need to build an algorithm that can generate valid Containers with masses in them, where validity is defined by the input parameters and the constraints. Ideally, this algorithm could be run in a loop to generate all possible valid Containers for a set of input parameters (the sample space should be small enough that it's at least theoretically possible to do so in a normal amount of time). But even a slimmed down "given a set of valid containers, give me another valid container or tell me that there are none".

Constants:

An ordered list of masses without repeating values. For the purpose of this, the index of the mass in the list can be thought of as the "label" and the actual mass is the "value". This list is constant for all values of the input parameters.
A function getTotalMass(container : Container) that reports the total adjusted mass of all the masses inside a container. Note that the adjusted mass is not simply the sum of the masses, there's a (moderately complex) set of rules that adjust for things including the total number of individual masses and some other (out of scope) parameters.

Inputs:

A minimum total mass for the container: minMass.
A maximum total mass for the container: maxMass.
A maximum number of individual items in the container: cap.

Constraints:

For any valid container c, minMass <= getTotalMass(c) <= maxMass.
For any valid container c, c.size <= cap.

A set of sample values/pseudocode:

//givens
masses = [1, 3, 4, 6] //masses have no pattern to their values, but they are all integers if that matters
function getTotalMass(container) { return sum(container) } // the real function is more complex

//parameters
minMass = 2
maxMass = 10
cap = 5

//valid combinations
[1, 1] //totalMass = 2
[1, 1, 1, 1, 1] //totalMass = 5, at cap
[1, 3, 1, 3, 1] //totalMass = 9, at cap
[4, 4, 1, 1] //totalMass = 10
[6, 4] //totalMass = 10
[3]
[4]
[6]
...

The numbers are such (ie small enough) that implementation simplicity is more important than algorithmic optimization.

Things I've considered:
Smallest first:

Start with the "biggest set of the smallest masses" (ie find the biggest objects where having cap of them fits inside maxMass. Memoize and return that.
When asked for the next valid container, start with that previous one and remove one from the smallest bin. If that gives enough room to add one of the next smallest size, do so. Memoize that as well and return. If it doesn't, remove another of the smallest ones and try again (until success).
On future iterations, always start with the previous one and do #2, checking if the result is equivalent to one already generated to ensure uniqueness.

Greedy (rocks and sand):

Start with the biggest single item that will fit in the bounds. Memoize and return.
On the next iteration, try to add successively smaller items one by one until something succeeds. Memoize and return.
Keep doing #2 until you can't add anything more.
After that, start by removing the largest object and add the next largest size. Memoize and return.
Do steps 2-4 as many times as needed until you run out of unique combinations.

Are there better ways?

topspin

@Benjamin-Hall this sounds a lot like KNAPSACK, which is NP-complete.
If you say input size doesn't matter too much (i.e. as in your example with cap=5), you should still be able to easily enumerate all solutions using brute-force recursion (stop early when min/max/capacity is exceeded, otherwise proceed without any fancy heuristics as you want the complete set anyway).
The wiki page should give some ideas for implementations, too.

Basically (not very thoroughly thought out pseudo-code mess):

def packing(masses, min, max, cap):
  if cap == 0:
    return []
  for e in masses:
    if e > max:    # this only works if your `getTotalMass` plays along
      continue
    for rest in packing(masses, min-e, max-e, cap-1):
      comb = e union rest
      if comb within constraints:
        yield comb

If your getTotalMass does not behave reasonably with the constraints, you probably need to just enumerate all possibilities up to capacity and check the constraints afterwards.

EDIT: guess if I make the function a generator the recursion should actually loop over it. Also, you have to pass in masses union empty for it to have a chance to create "light" results.

MZH

Treat the container like a string with letters coming from masses. Start with a container containing nothing, then iterate by creating the next string of the same size in lexicographic order and adding another mass when the container contains nothing but the last element of masses. Stop when the size of the container is greater than cap. This is similar to @topspin (generate all possible containers and filter), but with a different metaphor.

def generate_containers(masses, min_total_mass, max_total_mass, capacity):
    container = []
    while len(container) < capacity:
        if min_total_mass <= get_total_mass(container) <= max_total_mass:
            yield container
        container = next_container(container, masses)

    yield None # or whatever proper way to terminate a generator

def next_container(container, masses):
    # pythonism: masses[-1] is the last element of masses
    if all(m == masses[-1] for m in container):
        return [masses[0]] * (len(container) + 1) # create the next largest container with only first mass

    for i in range(len(container)):
        if container[i] == masses[-1]:
            container[i] = masses[0]
        else:
            container[i] = masses[masses.index(container[i]) + 1]
            return container