In base alla mia comprensione delle tue esigenze, non sono a conoscenza di un algoritmo pubblicato appositamente per il tuo caso, ma puoi crearne uno usando la seguente discussione.
Userò un esempio strano, ma vedrai perché presto.
Supponiamo che tu abbia una stringa come
AB1C4D6
Supponi che:
Il carattere nella posizione 3 può avere valori (1,2,3), ovvero 3 valori distinti.
Il carattere nella posizione 5 può avere valori (4,5), cioè 2 valori distinti.
Il carattere in posizione 7 può avere valori (6,7), cioè 2 valori distinti.
Di seguito sono riportati i possibili esiti dell'esecuzione di varie operazioni sostitutive sulla stringa originale.
Il numero totale di stringhe che possiamo ottenere è 3x2x2 = 12 (inclusa la stringa iniziale).
Questo processo è simile alla generazione di prodotti cartesiani di 3 set (come SELECT * FROM T1, T2, T3).
Dato una lunghezza di stringa di N lettere, se ogni lettera ha al massimo r_i possibili caratteri di sostituzione, allora avremmo un totale di (r_0 * r_1 * r_2 * ... * r_N) parole dove r_i = 1 se non ci sono rimpiazzi per la lettera.
Il motivo per cui ho scelto questo specifico esempio è che esiste una descrizione su come generare il prodotto cartisiano in qui che utilizza valori simili, quindi sarebbe facile da seguire (anche se non è né in Ruby né in Python).
Il concetto sarà lo stesso se si esegue il mapping di 1 carattere di input a più di 1 carattere purché si effettui un singolo passaggio alla stringa e si usi la funzione appropriata per eseguire la sostituzione.
