组合算法有很多问题和答案，但是在我所有的搜索中，我从未见过此问题。这和编码挑战一样，是数学上的挑战。
如果我有一组可区分的项目和一组未区分的盒子，如何找到盒子中所有项目的组合？请记住，不仅是我们想要的组合数量，程序还必须输出所有可能的组合。规则：
等效示例：
我可以用笔和纸坐下来画出所有的组合，但是我不知道我的大脑在使用什么算法。在此代码中，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所示的列表。我有一些涉及二叉树和迭代指针的想法，但是它们都没有起作用。它看起来像是一个可解决的问题，但如果从数学上讲不可能，我也希望得到反馈。谢谢！
（首选语言c ++，但我可以阅读最常用的编程语言）
这里是使用迭代器的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)
使用Prolog，特别是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).
代码来自：All partitions of a list in Prolog
示例产生期望的结果。
?- 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.
花了一整天的时间，最后，我有一个解决方案。感谢大家的所有帮助，如果您是大量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 << "}";
}
这是解决问题的一种非常大的方法，我相信有些人可以找到更多更简洁的方法，因此，如果您找到更优雅的算法，请分享。再次感谢！