перестановки из N шаров в M коробках в C ++

Question

Я задал вопрос на прошлой неделе о перестановках в C ++ ( Список комбинаций из N шаров в M полях в C ++ ).

Ответы мне очень помогли, но моя проблемасейчас изменилось.То, что я хотел бы сделать, это перевод этой функции Python на C ++, сохраняя тот же порядок в результате:

def combinations_with_replacement_counts(n, r):  #(n-boxes, r-balls)
   size = n + r - 1
   for indices in itertools.combinations(range(size), n-1):
       #print indices
       starts = [0] + [index+1 for index in indices]
       stops = indices + (size,)
       yield tuple(map(operator.sub, stops, starts))

У меня нет навыков в Python и, несмотря на мои чтения документа, я не понимаюне понимаю эту функцию.

Answer 1

Вы знаете, что Python интерпретируется, верно?Вы можете просто напечатать строки, которые вы не понимаете, непосредственно в python и посмотреть, что произойдет ... сначала начните с небольших значений.

Я не понимаю алгоритм itertools.combination ()

Документация здесь и включает пример вывода.Обратите внимание, что значение, возвращаемое из combinations, является ленивым, поэтому вам нужно принудительно оценить его:

>>> import itertools
>>> itertools.combinations(range(4), 2)
<itertools.combinations object at 0x979a964>
>>> list(itertools.combinations(range(4), 2))
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

Понятно, что теперь делает combinations?Если нет, поиграйте с ним.

... и синтаксис "stop = indices + (size,)"

Итак try это, это не будет кусаться:

>>> indices=list(itertools.combinations(range(4), 2))[0]
>>> size=4
>>> stops=indices + (size,)
>>> indices
(0, 1)
>>> stops
(0, 1, 4)

Синтаксис (x,) создает одноэлементный кортеж (инвариантная последовательность - как list, которую вы не можете изменить, но с круглыми скобками() вместо квадратных []).Вы можете использовать [x] для создания одноэлементного списка, но (x) будет неоднозначным, поскольку круглые скобки также используются для других целей, таких как аргументы функций и группировка.

Относительно map (), ...

Прочитайте документ , поиграйте с ним, это не сложно.

Answer 2

Этот код C ++, похоже, имеет те же результаты, что и ваш пример с python. Это далеко от идеального, но вы могли бы понять алгоритм и даже использовать эту реализацию.

#include <deque>
typedef std::deque<size_t> BoxList;

class Generator {
    size_t boxNum, ballNum, ownBox;
    Generator* recursive;
public:
    ~Generator() { if ( recursive == NULL ) delete recursive; }
    Generator( size_t boxes, size_t balls ) : boxNum(boxes), ballNum(balls) {
        if ( boxes > 1 ) {
            recursive = new Generator( boxes-1, balls );
            ownBox = 0;
        } else {
            recursive = NULL;
            ownBox = balls;
        }
    }
    BoxList operator()() {
        if ( ownBox > ballNum ) throw 1;
        if ( boxNum <= 1 ) return BoxList( 1, ownBox++ );
        try {
            BoxList res = recursive->operator()(); 
            res.push_front( ownBox );
            return res;
        }
        catch(...) {
            delete recursive;
            ownBox++;
            recursive = new Generator( boxNum-1, ballNum-ownBox );
            return operator()();
        }
    }
};

Интерфейс класса позволяет использовать его в качестве стандартного генератора. Оператор () сгенерирует исключение, когда все возможные параметры уже будут повторены.

Generator g( boxes, balls );
try{
    while( true )
        g();
}
catch(...) {}

Answer 3

Код Python, который вы цитировали, реализует алгоритм, который я описал в мой ответ на ваш вопрос : он перебирает возможные способы размещения r - 1 блок в n + r - 1 позиция, а затем составить список различий между соседними позициями (которые подсчитывают количество шариков, попавших в этот ящик).