Что не так с combinations_with_replacement?

Question

Все знают замечательную библиотеку itertools. И на первый взгляд метод combinations_with_replacement должен делать то, что мне надо, а именно перебрать все возможные комбинации строки:

from itertools import combinations_with_replacement


for i in combinations_with_replacement('xo', 3):
    print(''.join(i))

вывод будет ' xxx xxo xoo ooo ' . Но где же oxx, oox, xox... и т.д Как получить реально ВСЕ возможные комбинации строки?

Answer 1

Вот так вот:

import itertools

print(list(itertools.product('xo', repeat=3)))

Answer 2

Вам нужны не перестановки, а всевозможные комбинации из символов 'x' и 'o'.

Всевозможные комбинации находятся с помощью Декартова произведения (itertools.product).

from itertools import product


for i in product('xo', repeat=3):
    print(''.join(i))

print(len(list(itertools.product('qwertyuio', repeat=12)))) вызывает MemoryError. Как нибудь можно это обойти? Проще говоря я пытаюсь понять как мне написать брутфорс

При приведении генератора (а itertools.product возвращается именно генератор) к списку, выполняется высчитывание всех элементов генератора, чтобы их сохранить в список

Если вспомнить школьную математику, то количество комбинаций длины n k-элементного множества равно kⁿ. Для вашего случая:

In [1]: len('qwertyuio') ** 12
Out[1]: 282429536481

282429536481 комбинаций

Один кортеж с 12-ю символами (возвращаемые элементы генератора) занимает:

In [1]: import sys

In [2]: "a"*12
Out[2]: 'aaaaaaaaaaaa'

In [3]: tuple(_)
Out[3]: ('a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a')

In [4]: sys.getsizeof(_)
Out[4]: 136

136 байт

Итого, для хранения всех комбинаций понадобится 136 * 282429536481 = 38410416961416 байт (или, приблизительно, 38410.4 гигабайт) оперативной памяти +несущественные расходы на хранение списка и прочий мусор, но это мы считать не будем :)

Отсюда и ошибка MemoryError

Чтобы избежать ошибки, не надо пытаться хранить в памяти все значения, воспроизводимые генератором. Можно итерироваться сразу по генератору

for i in product('qwertyuio', repeat=12):
    ...

Answer 3

combinations_with_replacement увеличивает (в разных вариантах) количество отдельных элементов до достижения нужной длины. Эта функция НЕ ПЕРЕСТАВЛЯЕТ элементы местами и не вставляетимеющиеся в другие места.

Результаты oxx, oox, xox не могут получиться в этой функции, т.к. в них имеется другая последовательность символов - oх

БЛОГ НА HUSL

Что не так с combinations_with_replacement?

Ответы (3 шт):