Алгоритм для поиска всех способов распределения 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 вариантов (N-я степень M).

Таким образом, мы можем сгенерировать все числа в диапазоне 0..P-1 и считать их номерами оснований M-base.
Если k-я цифра числа в представлении M-базы равна 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