Комбинаторика — Как собрать все перестановки/комбинации (permutations/combinations) из двух разных групп?

Question

[Григорий Васильков]

Нашел в библиотеке python itertools код, который делает все возможные пересечения (combinations) в рамках одной группы. Также есть код, который делает все возможные перестановки в рамках одной группы (permutations);

Я не совсем понимаю, как поочередно используя эти два метода получить перестановки всех элементов, при условии, что нужно брать элементы из двух разных групп?

Практическое применение - slugger.

Есть буквосочетание например "ый". Нужно заменить его на такое же в ASCII, условно "iy".

Соотвественно нужно получить такие перестановки:
Группа 1: ы, Ы
Группа 2: й, Й
Ожидаемый результат: ый ыЙ Ый ЫЙ

Можно написать просто цикл в два уровня и получить то что нужно.
Интересно как это можно сделать, через "стандартные" функции комбинаторики.

Если я использую функцию комбинаторики для всех 4 букв, на выходе будут в том числе пересечения ыЫ йЙ и подобные.

То есть цель - понять как они применяются эти функции.

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

Answer 1

[PavelMos]

Если я использую функцию комбинаторики для всех 4 букв, на выходе будут в том числе пересечения ыЫ йЙ и подобные.
Т.к. важно условие что сочетаться могут только разные буквы, но не заглавная и маленькая одной и той же буквы, имхо можно делать признак b, m (большая, маленькая или 1,0) для N-столбцов.

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

upd:
это называется декартово произведение списка элементов самого на себя (product позволяет перемножать несколько списков) с заданным числом повторов

list(itertools.product('mB',repeat=3))
Out[9]: 
[('m', 'm', 'm'),
 ('m', 'm', 'B'),
 ('m', 'B', 'm'),
 ('m', 'B', 'B'),
 ('B', 'm', 'm'),
 ('B', 'm', 'B'),
 ('B', 'B', 'm'),
 ('B', 'B', 'B')]

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

Comments

[Григорий Васильков]

Могу я подробнее поспрашивать про эти функции?

Судя по теории тут есть три базовые операции - перемножение, пересечение и перестановка. Я просто пытаюсь нащупать когда какая нужна.

Я нашел ответ по своей задаче, оказывается у меня вполне себе перемножение - product()

Но тот же результат можно получить и перестановкой, отбросив лишнее, вопрос оптимальности.

И я что-то не могу критерий понять когда какая.

[Григорий Васильков]

И это, в упор не втыкаю как это можно прочесть и переписать

for pool in pools:
  result = [x+[y] for x in result for y in pool]

Как можно внутри некоего цикла результатом сделать обход самого результата внутри которого мерж того что было с новым элементом

[PavelMos]

Григорий Васильков, я возможно ошибся в терминологии, или декартово произведение (product) одного множества самого на себя в такой-то степени эквивалентно размещению с повторениями те x в степени y. В учебниках которые сейчас смотрел по этому вопросу - они в одном параграфе идут.

Перестановка это варианты, каждый из которых включает все элементы. Если было 4 элемента, то ширина выходного массива будет 4 и тд. Для сочетаний больших и малых букв это не подходит имхо. Если брать все варианты букв, то да, элементов будет 4: ыЫйЙ, но не все они сочетаются друг с другом

[PavelMos]

Григорий Васильков, так result перезаписывается каждый раз, аналогично x=x+1
Но каждый раз к тому, что сохранено в предыдущем result, добавляется элемент(ы) из pool
Тут еще есть
https://stackoverflow.com/questions/37348906/conve...

[Григорий Васильков]

PavelMos, блеск!