Найти все возможности Бин и объектов

Задано конечное множество ячеек и объектов, где ячейки имеют бесконечный размер (нет ограничений на количество объектов, которые они могут содержать. Что такое эффективный алгоритм для вычисления всех возможностей объектов в бункерах.

Например:

Допустим, у нас есть бины: B1, B2 и объекты O1, O2 решение будет: 

B1 => [O1, O2] 
B2 => []

B1 => []
B2 => [O1, O2]

B1 => [O2]
B2 => [O1]

B1 => [O1]
B2 => [O2]
2 2
algorithm combinations recursion

2 ответа:

Предположим, что B-это число ячеек, а O-число объектов. Алгоритм должен просто считать в base-B (в отличие от base-10 или base-2), считая от 0B до AA...AA B , где A = B - 1, а число цифр равно O.

Самый простой способ подсчета в base-B - это иметь массив длины O. На каждом шаге преобразования ...ХАА..АА до ...Y00..00, Где X < A и Y = X + 1, и часть АА..АА может даже иметь нулевую длину. Повторяйте как можно дольше. Самый простой способ преобразовать суб-массив это выполнение внутреннего цикла, который выполняется с одного конца массива, увеличивая элементы по модулю B и останавливаясь после первого элемента, который не равен нулю после инкремента, или на другом конце массива.

Интерпретация содержимого массива на каждом шаге состоит в том, что каждая из o цифр говорит нам, в каком bin-объекте On находится.
1

В моем понимании простое решение может быть следующим:

Предположим, что у нас есть два бункера (в соответствии с вашим упомянутым решением): 

B1 => [O1, O2] 
B2 => []

Это означает, что B1 имеет 2 объекта, А B2 пуст, поэтому 1, потому что 2^0 = 1

Итого = 3 и общее число возможностей = 2^3 = 8

Объединить все ячейки, если вы используете add all (не уверен, что это сложность, но вы можете взглянуть на коллекции.addAll [в частности java, будут другие алгоритмы с лучшей сложностью для слияния два или несколько массивов]), а затем вы можете найти все комбинации N элементов в O (n!) с алгоритмом, упомянутым здесь.

Лучший способ найти все комбинации

0