Список комбинаций из N шаров в M коробках в C ++

Question

Я хотел бы написать функцию, которая генерирует массив кортежей, содержащих все возможные перестановки из N шаров в M коробках в C ++.

Порядок (Edit: в результирующем списке) не важен, просто первый должен быть (N, 0, ..., 0), а последний (0,0, ..., N).

Я не нашел такой реализации в сети в C ++, только перестановки символов или вычисления количества перестановок ...

Есть идеи?

Answer 1

Есть хитрый способ решить эту проблему.Представьте, что мы взяли n шаров и m - 1 коробок и поместили их в ряд длиной n + m - 1 (с коробками, смешанными среди шаров).Затем поместите каждый шарик в коробку справа и добавьте m -й ящик справа, в который попадут все оставшиеся шары.

Это дает расположение n шаров в m коробках.

Легко видеть, что есть одинаковое количестворасположение n шаров в последовательности с m - 1 коробками (первое изображение), так как имеются расположения n шаров в m коробках,(Чтобы пойти в одну сторону, поместите каждый шарик в коробку справа; для движения в другую сторону каждая коробка опустошает шарики в позиции слева от нее.) Каждое расположение на первом рисунке определяется позициями, в которые мы помещаемкоробки.Есть m - 1 коробка и n + m - 1 позиция, таким образом, есть ^{n + m - 1} C _{m - 1} способов сделать это.

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

В Python это было бы очень просто, так как есть комбинаций алгоритм в стандартной библиотеке:

from itertools import combinations

def balls_in_boxes(n, m):
    """Generate combinations of n balls in m boxes.

    >>> list(balls_in_boxes(4, 2))
    [(0, 4), (1, 3), (2, 2), (3, 1), (4, 0)]
    >>> list(balls_in_boxes(3, 3))
    [(0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0), (3, 0, 0)]

    """
    for c in combinations(range(n + m - 1), m - 1):
        yield tuple(b - a - 1 for a, b in zip((-1,) + c, c + (n + m - 1,)))

Answer 2

Список комбинаций из N шаров в M коробках = k + Список комбинаций (N-k) шаров в (M-1) ящиках для каждого k от 0 до N. Попробуйте рекурсивно кодировать это.

Answer 3

Вы можете решить эту проблему рекурсивно, используя очередь векторов, где у вас есть функция с циклом for, который перебирает количество N шариков, помещая каждый из N шариков в один блок из представленных блоков M вектором размера M. Затем он рекурсивно вызывает ту же функцию, но передает уменьшенное значение индекса для того, чтобы установить значение N шаров в векторе. Базовый случай рекурсивных вызовов инициализирует очередь с векторами размера M и создаст N векторов, причем каждый вектор имеет интервал инициализации (в данном случае слот 0), установленный с индивидуальным значением из N шаров. 1001 *

Редактировать: Я изменил код, чтобы он теперь отражал мульти-комбинации, а не перестановки. Это потребовало добавления нового struct box_t, который позволяет использовать для правильного хранения ящиков в очереди и сообщать, когда мы нажимаем повторы.

struct box_t
{
    vector<int> boxes;
    int flag;  //this flag lets us know if we're repeating a value
    box_t(int num_boxes): boxes(num_boxes), flag(0) {}
};

typedef queue<box_t> comb_queue;

comb_queue multi_combinations(int num_boxes, int ball_index)
{
    if (ball_index == 0)
    {
        comb_queue initial_queue;

        //initialize our queue with M vectors that will have 
        //only one of the "boxes" initialized with a value
        for (int i=0; i < num_boxes; i++)
        {
            box_t temp(num_boxes);
            temp.boxes[i] += 1;
            initial_queue.push(temp);
        }

        return initial_queue;
    }

    //here is our recursive call
    comb_queue box_combinations = multi_combinations(num_boxes, ball_index - 1);
    int queue_size = box_combinations.size();

    for (int i=0; i < queue_size; i++)
    {
        box_t boxes = box_combinations.front();
        box_combinations.pop();

        if (boxes.flag)
        {
            //this combination has already been processed, so place back in the queue
            //and move on
            box_combinations.push(boxes);
            continue;
        }

        for (int j=0; j < num_boxes; j++)
        {
             //increment the ball-count in each of the boxes
             boxes[j] += 1;
             box_combinations.push(boxes);

             //remove the ball we just added from the box slot for the next loop
             boxes[j] -= 1;
        }

        //finally place the box_t we've been processing back in the queue, but with the
        //repeat flag set
        boxes.flag = 1;
        box_combinations.push(boxes);
    }

    return box_combinations;
}

Затем вызовите функцию как:

comb_queue all_multi_combinations = multi_combinations(M, (N-1));

Теперь выводом будет очередь векторов, в которых есть количество шаров в каждой клетке для каждой мульти-комбинации из N шаров в M коробках.

Answer 4

На самом деле есть один. Взгляните на: http://photon.poly.edu/~hbr/boost/combinations.html

Он не в ускорении, но следует тем же принципам, что легко видно из названия.