CODEWITHSUNDEEP
pythonpython-3.xcombinationspython-itertools
Saranyan Senthivel
Saranyan Senthivel

Reputation: 73

Create string combination based on replacement

Given a word and a dictionary of replacement characters, I need to form a Combination of characters based on the replacement

Input

word = 'accompanying'  
substitutions={'c':['$'], 'a': ['4'], 'g': ['9']}

Output

{'a$$ompanyin9', 'ac$ompanyin9','a$companyin9','4ccomp4nying', '4$$omp4nying', 
'4$comp4nying','4c$omp4nying', '4ccomp4nyin9', 'a$$ompanying', 'a$companying', 'ac$ompanying', 
'accompanyin9', 'accompanying', '4$$omp4nyin9', '4$comp4nyin9', '4c$omp4nyin9','etc.,'}

I wrote a code, But it does not provide me all the combinations which I am expecting

Sample Code

from itertools import product
substitutions={'c':['$'], 'a': ['4'], 'g': ['9']}
for key in substitutions.keys():
  if key not in substitutions[key]:
    substitutions[key].append(key)
wordPossibilities = []
word = 'accompanying'
for substitute in [zip(substitutions.keys(),ch) for ch in product(*substitutions.values())]:
  temp=word
  for replacement in substitute:
    temp=temp.replace(*replacement)
  wordPossibilities.append(temp)
print(set(wordPossibilities))

My Output

{'4$$omp4nyin9', 'a$$ompanyin9', 'a$$ompanying', 'accompanyin9',
'accompanying', '4ccomp4nyin9', '4$$omp4nying', '4ccomp4nying'}

My code replaces all characters in the provided string if found a replacement. How do I make replacements based on Indexes to find all possible combinations?

Upvotes: 2

Views: 165

Answers (2)

Prune
Prune

Reputation: 77850

Obviously, you need to rewrite your logic to consider individual instances of the desired letters, rather than each unique letter. Find all occurrences of desired letters; use itertools to get the power set; make the indicated substitutions for each element of the power set. power_set comes from this SO answer. I've left the code "exploded" in some places to show the logic more readily. You will likely want to wrap the final loop into a one-line return expression.

from itertools import chain, combinations

def power_set(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
                               
substitutions={'c':['$'], 'a': ['4', 'a'], 'g': ['9']}
word = 'accordingly'

# Get index of each desired letter and its poosible substitutions
sub_idx = [(pos, letter, sub_letter) for pos, letter in enumerate(word)
            if letter in list(substitutions.keys()) for sub_letter in substitutions[letter]]
print("Replacement set", sub_idx)

for possibility in power_set(sub_idx):
    # Make each of the substitutions indicated in the power set
    new_word = list(word)
    for pos, _, sub_letter in possibility:
        new_word[pos] = sub_letter
    print(''.join(new_word))

Output:

Replacement set [(0, 'a', '4'), (0, 'a', 'a'), (1, 'c', '$'), (2, 'c', '$'), (8, 'g', '9')]
accordingly
4ccordingly
accordingly
a$cordingly
ac$ordingly
accordin9ly
accordingly
4$cordingly
4c$ordingly
4ccordin9ly
a$cordingly
ac$ordingly
accordin9ly
a$$ordingly
a$cordin9ly
ac$ordin9ly
a$cordingly
ac$ordingly
accordin9ly
4$$ordingly
4$cordin9ly
4c$ordin9ly
a$$ordingly
a$cordin9ly
ac$ordin9ly
a$$ordin9ly
a$$ordingly
a$cordin9ly
ac$ordin9ly
4$$ordin9ly
a$$ordin9ly
a$$ordin9ly

Upvotes: 1

Ajax1234
Ajax1234

Reputation: 71461

It is clean and straightforward to use a generator with recursion:

word = 'accompanying'  
subs={'c':['$'], 'a': ['4'], 'g': ['9']} 
def get_subs(d, c = []):
  if not d:
     yield ''.join(c)
  else:
     for i in [d[0], *subs.get(d[0], [])]:
        yield from get_subs(d[1:], c+[i])

print(list(get_subs(word)))

Output:

['accompanying', 'accompanyin9', 'accomp4nying', 'accomp4nyin9', 'ac$ompanying', 'ac$ompanyin9', 'ac$omp4nying', 'ac$omp4nyin9', 'a$companying', 'a$companyin9', 'a$comp4nying', 'a$comp4nyin9', 'a$$ompanying', 'a$$ompanyin9', 'a$$omp4nying', 'a$$omp4nyin9', '4ccompanying', '4ccompanyin9', '4ccomp4nying', '4ccomp4nyin9', '4c$ompanying', '4c$ompanyin9', '4c$omp4nying', '4c$omp4nyin9', '4$companying', '4$companyin9', '4$comp4nying', '4$comp4nyin9', '4$$ompanying', '4$$ompanyin9', '4$$omp4nying', '4$$omp4nyin9']

However, itertools.product can be used for a shorter solution:

from itertools import product as prod
s = ''.join('{}' if i in subs else i for i in word)
result = [s.format(*i) for i in prod(*[[i, *subs[i]] for i in word if i in subs])]

Output:

['accompanying', 'accompanyin9', 'accomp4nying', 'accomp4nyin9', 'ac$ompanying', 'ac$ompanyin9', 'ac$omp4nying', 'ac$omp4nyin9', 'a$companying', 'a$companyin9', 'a$comp4nying', 'a$comp4nyin9', 'a$$ompanying', 'a$$ompanyin9', 'a$$omp4nying', 'a$$omp4nyin9', '4ccompanying', '4ccompanyin9', '4ccomp4nying', '4ccomp4nyin9', '4c$ompanying', '4c$ompanyin9', '4c$omp4nying', '4c$omp4nyin9', '4$companying', '4$companyin9', '4$comp4nying', '4$comp4nyin9', '4$$ompanying', '4$$ompanyin9', '4$$omp4nying', '4$$omp4nyin9']

Upvotes: 2

Related Questions