Функция combinations_with_replacement() модуля itertools в Python

Генерация сочетаний элементов списка с повторением

Синтаксис:

import itertools

itertools.combinations_with_replacement(iterable, r)

Параметры:

iterable - итерируемая последовательность,
r - int, длина возвращаемых кортежей.

Возвращаемое значение:

итератор.

Описание:

Функция combinations_with_replacement() модуля itertools возвращает итератор с комбинациями из элементов входной последовательности iterable, позволяя повторять в комбинациях отдельные элементы более одного раза. Каждая комбинация заключена в кортеж с длинной r элементов

Комбинации выдаются в лексикографическом порядке сортировки. Таким образом, если входные данные в итерируемой последовательности отсортированы, то комбинации в кортежах будут созданы в отсортированном порядке.

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

Количество возвращенных сочетаний равно (n+r-1)! / r! / (n-1)! если n > 0.

Функция itertools.combinations_with_replacement() примерно эквивалентна следующему коду:

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

Код комбинации combinations_with_replacement() также может быть выражен как подпоследовательность itertools.product() после фильтрации записей, в которых элементы расположены не в отсортированном порядке, а в соответствии с их положением во входном пуле:

from itertools import product

def combinations_with_replacement(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in product(range(n), repeat=r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

Примеры использования:

>>> from itertools import combinations_with_replacement
>>> x = [1, 2, 3]
>>> list(combinations_with_replacement(x, 2))
# [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
>>> list(combinations_with_replacement(x, 3))

# [
# (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3), 
# (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3)
# ]