Así que tengo una cadena '1xxx1' y quiero reemplazar un cierto número (quizás todos quizás ninguno) de x con un carácter, digamos '5'. Quiero todas las combinaciones posibles (... tal vez permutaciones) de la cadena donde x se sustituye o se deja como x. Me gustaría que esos resultados se almacenen en una lista.

Así que el resultado deseado sería

>>> myList = GenerateCombinations('1xxx1', '5')
>>> print myList
['1xxx1','15xx1','155x1','15551','1x5x1','1x551','1xx51']

Obviamente me gustaría poder manejar cadenas de cualquier longitud con cualquier cantidad de x, así como poder sustituir cualquier número. He intentado usar bucles y recursión para resolver esto sin éxito. Cualquier ayuda sería apreciada.