Программирование, комбинаторика, python

Проходим по строке и считываем индексы всех O в отдельный список.

 mystr = "XOXOXO"

idxs = [i for i in range(len(mystr)) if mystr[i] == 'O'] 

Комбинации делаем на базе списка индексов. Затем заменяем элементы по этим индексам в строке. И исходную строку надо где-то прихранить.

 combs = permutations(....) # сочетания номеров от 0 до len(idsx) - 1 вкл.

for c in combs:

    newstr = mystr

    for i in c: newstr[idxs[i]] = 'X'

    print(newstr) 

Суть в том, что однократное копирование строки целиком и изменение отдельных символов по индексу намного быстрее, чем сбор строки из кусков.

Если всё ещё будет долго, то можно выкинуть копирование из цепочки:

 combs = permutations(....) # сочетания номеров от 0 до len(idsx) - 1 вкл.

for c in combs:

    for i in c: mystr[idxs[i]] = 'X'

    print(mystr)

    for i in c: mystr[idxs[i]] = 'O' 

Не знаю, какой длины у вас строки, но на таких данных занимает какие-то миллисекунды:

 from itertools import permutations 

mystr = "XOXOXOXOXOXO"

idxs = [i for i in range(len(mystr)) if mystr[i] == 'O']



combs = permutations(idxs, 4)



mylst = list(mystr)

for c in combs:

    for i in c: mylst[i] = 'X'

    print(''.join(mylst))

    for i in c: mylst[i] = 'O' 

Правда, если строку удвоить, то будет заметно дольше, но и тогда основную часть времени занимает print.