找到将 N 个对象分配到 M 个集合中的所有方法的算法

Question

给定一个包含 M 个子集合的集合，有什么好的算法（最好是 Javascript 中的实现，但任何其他语言或伪代码也很好）找到 N 个对象在 M 中的所有可能分布子集？

例如，给定这样的设置：

var collection = [[],[],[]];
var items = ['a','b','c']

我希望结果看起来像这样

[['a','b','c'],[],[]]
[['a','b'],['c'],[]]
[['a','c'],['b'],[]]
[['a'],['b','c'],[]]
[['b','c'],['a'],[]]
[['b'],['c','a'],[]]
[['c'],['b','a'],[]]
[['a'],['b'],['c']]
[[],['a','b','c'],[]]
[[],['a'],['b','c']]
// etc

N 可以大于、小于或等于 N。此外，在示例中，我使用字符作为要分发的项目，但我希望算法能够分发对象任何类型。

Answer 1

每个对象都应该属于某个集合，因此存在 M 个变体。
对于 N 个对象，有 P=M^N 个变体（M 的 N 次方）。

因此我们可以生成0..P-1范围内的所有数字，并将它们视为M基基数。
如果M-base表示中数字的第k位是j，则第k个对象属于第j个集合。

您的案例示例 N=3, M=3, P=27 数字12(dec)等于110(three-radix)，所以合集是

[[a], ['b','c'],[]]

伪代码

for iii = 0 to Power(M, N) - 1
    Clear Collections
    i = iii //number of combination

    for k = 0 to N - 1 do

        j = i mod M     //integer modulo, % 
        //gives k-th digit of number i in M-radix representation
        //counting from right to left

        Collections[j].Add(Object[k])

        i = i div M     //integer division
    output Collections

找到将 N 个对象分配到 M 个集合中的所有方法的算法

Algorithm to find all ways to distribute N objects into M collections

javascript

algorithm

partitioning

combinatorics