Все комбинации предметов в коробках

Question

Существует множество вопросов и ответов для комбинированных алгоритмов, но во всех моих поисках я нигде не видел этой проблемы. Это такая же математическая задача, как и задача кодирования.

Проблема:

Если у меня есть набор отличительных предметов и набор незаметных ящиков, как мне найти все? комбинации предметов в коробках?
Имейте в виду, что нам нужно не просто количество комбинаций, которые должна выводить программа, все возможные комбинации.

Правила:

• Все объекты должны использоваться
• Порядок размещения объектов в поле не имеет значения
• Порядок Ящики расположены неважно
• У ящиков нет ограничений на количество предметов, которые они могут содержать
• Единственное, что отличает ящик, это предметы, которые он содержит

Примеры эквивалентности:

• [ab] [cd] [] эквивалентно [ab] [] [cd]
• [abcd] [] [] is равно [bdac] [] []
• [ab] [c] [d] эквивалентно [ab] [d] [c]

---

могу сядьте с ручкой и бумагой, чтобы вытянуть все комбинации, но я не могу понять, какой алгоритм использует мой мозг.
В этом коде a, b, c и d являются элементами.

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);

Ожидаемый результат:

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}, {}, {} }
}

Я ищу логический алгоритм, который выполняет работу FillBoxes() и выводит список, как показано в sorted.
У меня был несколько идей с участием бинарных деревьев и итерационных указателей b но никто из них не работал. Это выглядит как решаемая проблема, но если это математически невозможно, я также буду признателен за обратную связь.
Спасибо!

---

(предпочтительный язык c ++, но я могу читать самые распространенные языки программирования)

Answer 1

Использование Пролог , в частности 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).

Код из: Все разделы списка в Прологе

Пример генерации желаемого результата.

?- 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 2

Вот решение Python, использующее итераторы, чтобы оно не занимало много памяти.

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 3

Потратил на это целый день и, наконец, у меня есть решение. Спасибо всем за помощь, и если вы являетесь поклонником больших блоков кода C ++, получайте удовольствие !!

#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 << "}";
}

Это очень большой способ решения этой проблемы, и я уверен, что есть люди, которые могли бы найти более изящные методы, поэтому, если вы найдете более элегантный алгоритм, пожалуйста, поделитесь.
Еще раз спасибо!