给出一个算法(或直接使用Python代码),将N个物品分成K个容器的所有可能组合列举出来,其中每个容器至少包含一个物品。我需要两种情况:一种是考虑顺序,另一种是不考虑顺序。
例子(考虑顺序):
这些函数应该生成惰性迭代器/生成器,而不是列表。最好使用
虽然我在 Python 中提出了这个问题,但我也愿意翻译一个清晰的算法。
例子(考虑顺序):
>>> list(partition_n_in_k_bins_ordered((1,2,3,4), 2))
[([1], [2,3,4]), ([1,2], [3,4]), ([1,2,3], [4])]
>>> list(partition_n_in_k_bins_ordered((1,2,3,4), 3))
[([1], [2], [3,4]), ([1], [2,3], [4]), ([1,2], [3], [4])]
>>> list(partition_n_in_k_bins_ordered((1,2,3,4), 4))
[([1], [2], [3], [4])]
不需要考虑顺序的示例
>>> list(partition_n_in_k_bins_unordered({1,2,3,4}, 2))
[{{1}, {2,3,4}}, {{2}, {1,3,4}}, {{3}, {1,2,4}}, {{4}, {1,2,3}},
{{1,2}, {3,4}}, {{1,3}, {2,4}}, {{1,4}, {2,3}}]
这些函数应该生成惰性迭代器/生成器,而不是列表。最好使用
itertools
中找到的原语。我怀疑有一种聪明的解决方案正逃脱着我的注意力。虽然我在 Python 中提出了这个问题,但我也愿意翻译一个清晰的算法。