CODEWITHSUNDEEP
pythonalgorithmdictionaryiterationpermutation
Parseltongue
Parseltongue

Reputation: 11697

Find all combinations of letters, selecting each letter from a different key in a dictionary

Let's say we have this data structure:

class Lock:
def __init__(self):
    self.data1 = ['a', 'd', 'e', 'l', 's']
    self.data2 = ['s', 'i', 'r', 't', 'n']
    self.data3 = ['b', 'o', 'e', 'm', 'k']
    self.data4 = ['f', 'y', 'u', 'n', 'g']

Alternatively, 

d = {'1': ['a', 'd', 'e', 'l', 's'], '2': ['s', 'i', 'r', 't', 'n'], '3': ['b', 'o', 'e', 'm', 'k'], '4': ['f', 'y', 'u', 'n', 'g'] }

I want to find every possible combination of letters, given that each letter is selected from a different key or array. Order matters, so that the first letter always has to be from 'data1', second has to be from 'data2', etc.

The purpose is to then check these against a dictionary to see which ones are english-valid words. I assumed getting a list of all the combinations, and then doing the check would be the fastest, but if that's not the case, I'd like some input.

Upvotes: 1

Views: 3889

Answers (4)

Sanidhya Kumar
Sanidhya Kumar

Reputation: 11

x={'1':['a','b'], '2':['c','d']}
list1 = x.get('1')
list2 = x.get('2')
  for i in range(2):
    for j in range(2):          
      print(list1[i]+list2[j])

Upvotes: -1

Mike
Mike

Reputation: 466

Not using itertools:

 def combination(x):
     list1 = g.values()[0]
     list2 = g.values()[1]
     for i in list1:
         for j in list2:
              print(i+j)
 combination({'1':['a','b'], '2':['c','d']})

Upvotes: 1

Martijn Pieters
Martijn Pieters

Reputation: 1124070

Use itertools.product():

for combo in itertools.product(self.data1, self.data2, self.data3, self.data4):
    # combo is a tuple of 4 characters.

or:

for combo in itertools.product(*[d[k] for k in sorted(d.keys())]):
    # combo is a tuple of 4 characters.

Demo:

>>> import itertools                                                                                                                >>> d = {'1': ['a', 'd', 'e', 'l', 's'], '2': ['s', 'i', 'r', 't', 'n'], '3': ['b', 'o', 'e', 'm', 'k'], '4': ['f', 'y', 'u', 'n', 'g'] }
>>> for combo in itertools.product(*[d[k] for k in sorted(d.keys())]):
...     print ''.join(combo)
... 
asbf
asby
asbu
asbn
asbg
asof
asoy
asou
ason
asog
asef

...

snkf
snky
snku
snkn
snkg

Upvotes: 8

Emmanuel
Emmanuel

Reputation: 14209

Good answer from Martin, itertools.product is the best way. Since it was introduced in version 2.6, you can get back to old-fashioned style for Python 2.5 and earlier:

>>> [i1 + i2 + i3 + i4 for i1 in data1 for i2 in data2 for i3 in data3 for i4 in data4 ]
['asbf', 'asby', 'asbu', 'asbn', 'asbg', 'asof', 'asoy', 'asou', 'ason', 'asog', 'asef',
 'asey', 'aseu', 'asen', 'aseg', 'asmf', 'asmy', 'asmu', 'asmn', 'asmg', 'askf', 'asky', 
 'asku', 'askn', 'askg', 'aibf', 'aiby', 'aibu', 'aibn', 'aibg', 'aiof', 'aioy', 'aiou', 
 'aion', 'aiog', 'aief', 'aiey', 'aieu', 'aien', 'aieg', 'aimf', 'aimy', 'aimu', 'aimn', 
 'aimg', 'aikf', 'aiky', 'aiku', 'aikn', 'aikg', 'arbf', 'arby', 'arbu', 'arbn', 'arbg', 
 'arof', 'aroy', 'arou', 'aron', 'arog', 'aref', 'arey', 'areu', 'aren', 'areg', 'armf', 
 'army', 'armu', 'armn', 'armg', 'arkf', 'arky', 'arku', 'arkn', 'arkg', 'atbf', 'atby', 
 'atbu', 'atbn', 'atbg', 'atof', 'atoy', 'atou', 'aton', 'atog', 'atef', 'atey', 'ateu'
 ...

Upvotes: 3

Related Questions