All Combinations of Items in Boxes

Question

There are lots of questions and answers for combination algorithms but in all my searching I haven't seen this problem anywhere before. This is as much a mathematical challenge as a coding challenge.

The Problem:

If I have a set of distinguished items and a set of undistinguished boxes, how do I find all the combinations of items in boxes?
Bear in mind, it's not just the number of combinations that we want, the program must output, all the possible combinations.

Rules:

• All the objects must be used
• The order the objects are placed in the box doesn't matter
• The order the boxes are positioned in doesn't matter
• Boxes have no limit on the number of items they can contain
• The only thing that distinguishes a box is the items it contains

Examples of equivalency:

• [ab][cd][ ] is equivalent to [ab][ ][cd]
• [abcd][ ][ ] is equivelent to [bdac][ ][ ]
• [ab][c][d] is equivalent to [ab][d][c]

---

I can sit down with a pen and paper to draw out all the combinations but I can't work out what algorithm my brain is using.
In this code a, b, c and d are items.

std::vector<char> unsorted = { 'a', 'b', 'c', 'd' };
int box_count = 3;

std::vector<std::vector<std::vector<char>>> sorted = {};
sorted = FillBoxes(unsorted, box_count);

Expected Result:

sorted = {
    { {a}, {b}, {c,d}},
    { {a}, {b,c}, {d} },
    { {a}, {b,d}, {c} },
    { {a}, {b,c,d}, {} },
    { {a,b}, {c}, {d} },
    { {a,b}, {c,d}, {} },
    { {a,c}, {b}, {d} },
    { {a,c}, {b,d}, {} },
    { {a,d}, {b}, {c} },
    { {a,d}, {b,c}, {} },
    { {a,b,c}, {d}, {} },
    { {a,b,d}, {c}, {} },
    { {a,c,d}, {b}, {} },
    { {a,b,c,d}, {}, {} }
}

I am looking for a logical algorithm that does the job of FillBoxes(), and outputs the list as seen in sorted.
I have had a few ideas involving binary trees and iterative pointers but none of them have worked. It looks like a solvable problem but if it is mathematically impossible, I'd appreciate the feedback too.
Thanks!

---

(prefered language c++ but I can read most common programming languages)

Answer 1

Here is a Python solution using iterators so that it does not consume a lot of memory.

def sorted_box_partitions (boxes, things):
    if boxes == 0 and len(things) == 0:
        yield [set(things)]
    elif boxes < 1:
        yield None
    elif boxes == 1:
        yield [set(things)]
    elif len(things) == 0:
        yield [set() for _ in range(boxes)]
    else:
        sorted_things = sorted(things)
        min_thing = sorted_things[0]
        rest_things = sorted_things[1:]

        # First do all partitions with min_thing and others.
        for partition in sorted_box_partitions(boxes, rest_things):
            partition[0].add(min_thing)
            yield partition

        # Now do all partitions with min_thing by itself.
        for partition in sorted_box_partitions(boxes - 1, rest_things):
            yield [set([min_thing])] + partition

for p in sorted_box_partitions(4, ['a', 'b', 'c', 'd']):
    print(p)

Answer 2

Using Prolog, specifically SWI-Prolog

list_taken_rest([], [], []).
list_taken_rest([X|Xs], [X|Ys], Zs) :-
   list_taken_rest(Xs, Ys, Zs).
list_taken_rest([X|Xs], Ys, [X|Zs]) :-
   list_taken_rest(Xs, Ys, Zs).

list_partitioned([], []).
list_partitioned([X|Xs], [[X|Ys]|Pss]) :-
   list_taken_rest(Xs, Ys, Zs),
   list_partitioned(Zs, Pss).

Code from: All partitions of a list in Prolog

Example generating desired result.

?- list_partitioned([a,b,c,d], [A]).
A = [a, b, c, d] ;
false.

?- list_partitioned([a,b,c,d], [A,B]).
A = [a, b, c], B = [d] ;
A = [a, b, d], B = [c] ;
A = [a, b],    B = [c, d] ;
A = [a, c, d], B = [b] ;
A = [a, c],    B = [b, d] ;
A = [a, d],    B = [b, c] ;
A = [a],       B = [b, c, d] ;
false.

?- list_partitioned([a,b,c,d], [A,B,C]).
A = [a, b], B = [c],    C = [d] ;
A = [a, c], B = [b],    C = [d] ;
A = [a, d], B = [b],    C = [c] ;
A = [a],    B = [b, c], C = [d] ;
A = [a],    B = [b, d], C = [c] ;
A = [a],    B = [b],    C = [c, d] ;
false.

Answer 3

Spent the whole day on it and at last, I have a solution. Thanks for all the help everyone, and if you're a fan of large blocks of c++ code, have fun!!

#include <iostream>
#include <vector>

bool CheckEnd(int base, int digits, std::vector<int> number) {
    int j = 0;
    for (int i = 0; i < digits; ++i) {
        if (i >= base) {
            j = base - 1;
        } else {
            j = i;
        }
        if (number[i] < j) {
            return false;
        }
    }
    return true;
}

bool CheckValid(std::vector<int> number) {
    int max = 0;
    for (int value : number) {
        if (value > max + 1) {
            return false;
        }
        if (value > max) {
            max = value;
        }
    }
    return true;
}

std::vector<std::vector<int>> BaseCounter(int base, int digits) {
    int start = 0;
    std::vector<int> number(digits, start);
    int *start_point = &(number[digits - 1]);
    int *point = start_point;
    std::vector<std::vector<int>> flipped_list;

    bool loop = true;
    while (loop) {
        if (CheckEnd(base, digits, number)) {
            loop = false;
        }
        if (CheckValid(number)) {
            flipped_list.push_back(number);
        }
        point = start_point;
        ++ *point;
        while ((*point == base)) {
            *point = start;
            -- point;
            ++ *point;
        }
    }
    return flipped_list;
}

std::vector<std::vector<std::vector<char>>> FillBoxes(
    std::vector<char> unsorted,
    int box_count) {

    int index = 0;
    bool loop = true;
    std::vector<std::vector<int>> flipped_list =
        BaseCounter(box_count, unsorted.size());
    std::vector<std::vector<std::vector<char>>> sorted;
    for (int i = 0; i < flipped_list.size(); ++i) {
        std::vector<std::vector<char>> boxes(box_count);
        for (int passenger_index = 0;
            passenger_index < unsorted.size();
            ++ passenger_index) {
            index = flipped_list[i][passenger_index];
            boxes[index].push_back(unsorted[passenger_index]);
        }
        sorted.push_back(boxes);
    }
    return sorted;
}


int main()
{
    std::vector<char> unsorted = { 'a', 'b', 'c', 'd' };
    int box_count = 3;

    std::vector<std::vector<std::vector<char>>> sorted;
    sorted = FillBoxes(unsorted, box_count);



    std::cout << "{ \n";
    for (std::vector<std::vector<char>> v1 : sorted) {
        std::cout << "{ ";
        for (std::vector<char> v2 : v1) {
            std::cout << "{ ";
            for (char v3 : v2) {
                std::cout << v3 << " ";
            }
            std::cout << "} ";
        }
        std::cout << "}\n";
    }
    std::cout << "}";
}

This is a very large way of solving it and I'm sure there are people who could find far more neat methods so if you do find a more elegant algorithm, please do share.
Thanks again!