Как сгенерировать все комбинации назначения шаров в корзины, включая пустые и полные задания?

Question

Кажется, это известная проблема, но я не могу ее найти. У меня есть m шары и n корзины. Я хотел бы сгенерировать все возможные комбинации размещения шаров в бункерах, включая полные и пустые задания, т. Е. Бин может быть пустым или содержать все шары (см. Пример ниже).

Например, для m=n=2 я нашел:

1    x    bin 1 contains ball 1, bin 2 contains nothing.
x    1    bin 1 contains nothing, bin 2 contains ball 1.
2    x    bin 1 contains ball 2, bin 2 contains nothing.
x    2    bin 1 contains nothing, bin 2 contains ball 2.
1,2  x    bin 1 contains balls 1 and 2, bin 2 contains nothing.
x    1,2  bin 1 contains nothing, bin 2 contains balls 1 and 2.
1    2    bin 1 contains ball 1, bin 2 contains ball 2.
2    1    bin 1 contains ball 2, bin 2 contains ball 1.
x    x    bin 1 contains nothing, bin 2 contains nothing.

Как я могу сгенерировать эти комбинации в Python (например)? Вы можете предоставить псевдокод или любой другой язык программирования.

Я начинаю с генерации всех комбинаций, таких как

x
1
2
1,2

, затем я подумывал назначить эти комбинации бинам, но я могне заканчивай это.

Answer 1

Вот решение в Matlab , полностью векторизация . Это должно быть довольно быстро. Подход заключается в следующем:

1. Создайте матрицу, которая указывает, к какой корзине идет каждый шар (включая возможность отсутствия корзины);
2. Соберите шары, которые есть в каждой корзине.

Первая часть - это просто декартово произведение n+1 -элементного вектора с самим собой m раз. Это можно сделать как числовое базовое преобразование с помощью dec2base, при условии, что n меньше 36. Если нет, то можно использовать этот подход .

Вторая часть выполнена эффективно с accumarray.

m = 2; % data: number of balls
n = 3; % data: number of bins
t = (n+1)^m; % compute number of cases
[~, pos] = ismember(dec2base(0:t-1, n+1), ['1':'9' 'A':'Z']); % each column in this
% matrix refers to a ball, and tells which bin the ball goes to, or zero if no bin
[ii, jj, vv] = find(pos); % ii: combination; jj: ball: vv: bin
result = accumarray([ii vv], jj, [t n], @(x){sort(x).'}); % collect balls of each bin

Пример

Для m=2, n=3:

(извините за использование изображения).

Answer 2

для m шаров, помещаемых в n бинов, существует n ^ m комбинаций. Но поскольку вы соглашаетесь не ставить шары на шары m-1, ответом на ваш вопрос является суммирование m ^ 0 + mC1 * n ^ 1 + mC2 * n ^ 2 + .... mCm * n ^ m

например. для 3 шаров в 3 бина, общее число составляет 1 + 3 * 3 + 3 * 9 + 1 * 27 = 64

Python Solution.

import itertools
#let bins be 'ABC', but u can have your own assignment
bins = 'ABC'
balls = '123'
tmp = []
for no_ball_used in range(len(balls)+1):
    bin_occupied = [''.join(list(i)) for i in itertools.product(bins,repeat=no_ball_used)]
    ball_used = [''.join(list(i)) for i in itertools.combinations(balls,no_ball_used)]
    solution = [i for i in itertools.product(ball_used,bin_occupied)]
    tmp.append(solution)

tmp - полный список,где первая часть используется как шарик, а вторая - как корзина.

print(tmp)
[[('', '')], [('1', 'A'), ('1', 'B'), ('1', 'C'), ('2', 'A'), ('2', 'B'), ('2', 'C'), ('3', 'A'), ('3', 'B'), ('3', 'C')], [('12', 'AA'), ('12', 'AB'), ('12', 'AC'), ('12', 'BA'), ('12', 'BB'), ('12', 'BC'), ('12', 'CA'), ('12', 'CB'), ('12', 'CC'), ('13', 'AA'), ('13', 'AB'), ('13', 'AC'), ('13', 'BA'), ('13', 'BB'), ('13', 'BC'), ('13', 'CA'), ('13', 'CB'), ('13', 'CC'), ('23', 'AA'), ('23', 'AB'), ('23', 'AC'), ('23', 'BA'), ('23', 'BB'), ('23', 'BC'), ('23', 'CA'), ('23', 'CB'), ('23', 'CC')], [('123', 'AAA'), ('123', 'AAB'), ('123', 'AAC'), ('123', 'ABA'), ('123', 'ABB'), ('123', 'ABC'), ('123', 'ACA'), ('123', 'ACB'), ('123', 'ACC'), ('123', 'BAA'), ('123', 'BAB'), ('123', 'BAC'), ('123', 'BBA'), ('123', 'BBB'), ('123', 'BBC'), ('123', 'BCA'), ('123', 'BCB'), ('123', 'BCC'), ('123', 'CAA'), ('123', 'CAB'), ('123', 'CAC'), ('123', 'CBA'), ('123', 'CBB'), ('123', 'CBC'), ('123', 'CCA'), ('123', 'CCB'), ('123', 'CCC')]]

tmp [0] = комбинация из 0 шаров

tmp [1] = комбинация из 1 шаров

tmp [2] = комбинация из 2 шаров

tmp [3] = комбинация из 3 шаров

Вы можете распаковать tmp с помощью

[item for sublist in tmp for item in sublist]

Answer 3

Хорошо, вот ограниченное решение для двух бинов, но произвольное количество (различимых) шаров.

Он начинается с поиска возможных комбинаций шаров, которые можно положить в корзину 1 (combsBin1). Оттуда все эти комбинации повторяются, и генерируется подмножество шаров, исключая те, которые уже помещены в корзину 1. Затем для каждой комбинации в combsBin1 все комбинации для заполнения корзины 2 находятся. Наконец, комбинация этих комбинаций (но я прошу прощения за плохую формулировку) сохраняется.

Здесь приведен код Octave (совместимый с MATLAB). Это определенно не красиво, и это может помочь удалить некоторые точки с запятой для проверки промежуточных результатов.

balls = [NaN 1 2];
bins = [1 2];

finalCombs = {};

% Fill bin 1
combsBin1 = {};
for iBall = 1:numel(balls)-1
  if (iBall == 1)
    temp = nchoosek(balls, iBall);
  else
    temp = nchoosek(balls(2:end), iBall);
  end
  combsBin1 = [combsBin1; mat2cell(temp, ones(size(temp, 1), 1))];
end

% Output
printf('Possible combinations for bin 1 only:\n\n');
printf('Bin 1\n');
printf('-----\n');
for iC = 1:size(combsBin1, 1)
  printf('%s\n', num2str(combsBin1{iC, 1}));
end

% Fill bin 2 by iterating all combinations found for bin 1
% and excluding all balls which are already in bin 1.
for iComb = 1:numel(combsBin1)
  b = [NaN setdiff(balls(2:end), combsBin1{iComb})];
  if (isnan(b))
    finalCombs = [finalCombs; [combsBin1{iComb}, {NaN}]];
  end
  for iBall = 1:numel(b)-1
    if (iBall == 1)
      temp = nchoosek(b, iBall);
    else
      temp = nchoosek(b(2:end), iBall);
    end
    c = mat2cell(temp, ones(size(temp, 1), 1));
    for iC = 1:numel(c)      
      finalCombs = [finalCombs; [combsBin1{iComb}, c(iC)]];
    end
  end
end

% Output
printf('\n\nPossible combinations for bin 1 and bin 2:\n\n');
printf('Bin 1          Bin 2\n');
printf('-----          -----\n');
for iC = 1:size(finalCombs, 1)
  str = num2str(finalCombs{iC, 1});
  printf('%s', str);
  printf('%s', char(32 * ones(1, 15 - length(str))));
  printf('%s\n', num2str(finalCombs{iC, 2}));
end

Я добавляю «NaN шарик», так как шарик не помещается в определенную корзину. Все возможные комбинации для набора шаров можно найти, используя nchoosek для увеличения количества шаров. Чтобы хранить различное количество шаров в комбинации, мне нужно использовать массивы ячеек, что делает обработку еще более сложной, и, возможно, код еще сложнее для понимания.

Для двух бинов и двух шаров мы получаем следующеевыходные данные:

Possible combinations for bin 1 only:

Bin 1
-----
NaN
1
2
1  2


Possible combinations for bin 1 and bin 2:

Bin 1          Bin 2
-----          -----
NaN            NaN
NaN            1
NaN            2
NaN            1  2
1              NaN
1              2
2              NaN
2              1
1  2           NaN

Если мы используем три шара, мы получим:

Possible combinations for bin 1 only:

Bin 1
-----
NaN
1
2
3
1  2
1  3
2  3
1  2  3


Possible combinations for bin 1 and bin 2:

Bin 1          Bin 2
-----          -----
NaN            NaN
NaN            1
NaN            2
NaN            3
NaN            1  2
NaN            1  3
NaN            2  3
NaN            1  2  3
1              NaN
1              2
1              3
1              2  3
2              NaN
2              1
2              3
2              1  3
3              NaN
3              1
3              2
3              1  2
1  2           NaN
1  2           3
1  3           NaN
1  3           2
2  3           NaN
2  3           1
1  2  3        NaN

Итак, теперь, чтобы обобщить этот код для поддержки произвольного числа бинов, вы должны поставить второечасть (исключая уже выбранные шары из ранее и т. д.) в некоторый итеративный, возможно, рекурсивный процесс. Это может быть много работы, но представленный подход, тем не менее, должен подойти.

Надеюсь, это поможет!