With variable length list of variable length strings, how do I create all combinations

Question

In python 3, I have a variable length list, where each element of the list is a variable length string. Something like this

['TO', 'G', 'ZDO', 'DEO', 'SGT', 'D', 'Z', 'FT', 'OV']

and I want to iterate over every possible combination of words where the letters that make up the word are from the strings in the list, and the length of the word is the same as the length of the list. So something like this

TGZDSDZFO
TGZDSDZFV
TGZDSDZTO
...
OGOOTDZTO
OGOOTDZTV

I am having trouble coming up with a generic solution for n-sized list.

How do you know how many characters to extract for every string in the list — Tim
– Tim, Commented Dec 16, 2014 at 18:58
Time, I want one character at a time from each string. Each string in the list contains the possible characters that make up the word at that position in the word. — Walter Anderson
– Walter Anderson, Commented Dec 16, 2014 at 18:59

Ignacio Vazquez-Abrams · Accepted Answer · 2014-12-16 19:01:24Z

8

>>> (''.join(s) for s in itertools.product(*['TO', 'G', 'ZDO', 'DEO', 'SGT', 'D', 'Z', 'FT', 'OV']))
<generator object <genexpr> at 0x7f2a46468f00>
>>> # to demonstrate:
... 
>>> list(itertools.islice((''.join(s) for s in itertools.product(*['TO', 'G', 'ZDO', 'DEO', 'SGT', 'D', 'Z', 'FT', 'OV'])), 3))
['TGZDSDZFO', 'TGZDSDZFV', 'TGZDSDZTO']

answered Dec 16, 2014 at 19:01

Ignacio Vazquez-Abrams

804k160 gold badges1.4k silver badges1.4k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ignacio Vazquez-Abrams Over a year ago

itertools.product() does the product of all of its arguments. The * separates the list into separate arguments for the function call. ''.join() joins with no separators. The rest is just a normal genex.

Community · Accepted Answer · 2017-05-23 12:05:52Z

2

As others have suggested, itertools is perhaps the simplest/easiest way to solve this. If you are looking to write your own algorithm however (i.e. reimplement what itertools does under the hood), then take a look at this:

def allPerms(L, sofar=''):
    if not L:
        print(sofar)
    else:
        for char in L[0]:
            allPerms(L[1:], sofar+char)

Output:

In [97]: L = ['TO', 'G', 'ZDO', 'DEO', 'SGT', 'D', 'Z', 'FT', 'OV']

In [98]: allPerms(L)
TGZDSDZFO
TGZDSDZFV
TGZDSDZTO
TGZDSDZTV
TGZDGDZFO
TGZDGDZFV
TGZDGDZTO
TGZDGDZTV
TGZDTDZFO
TGZDTDZFV
TGZDTDZTO
TGZDTDZTV
TGZESDZFO
TGZESDZFV
TGZESDZTO
TGZESDZTV
TGZEGDZFO
TGZEGDZFV
TGZEGDZTO
TGZEGDZTV
--- truncated ---

EDIT:

As @njzk2 points out, python3's yield-from does a fantastic job of making the output usable:

def allPerms(L, sofar=''):
    if not L: yield sofar
    else:
        for char in L[0]: yield from allPerms(L[1:], sofar+char)

Output:

In [118]: for i in allPerms(L): print(i)
TGZDSDZFO
TGZDSDZFV
TGZDSDZTO
TGZDSDZTV
TGZDGDZFO
TGZDGDZFV
TGZDGDZTO
TGZDGDZTV
TGZDTDZFO
TGZDTDZFV
TGZDTDZTO
TGZDTDZTV
TGZESDZFO
TGZESDZFV
TGZESDZTO
TGZESDZTV
TGZEGDZFO
TGZEGDZFV
TGZEGDZTO
TGZEGDZTV
TGZETDZFO
TGZETDZFV
TGZETDZTO
--- truncated ---

edited May 23, 2017 at 12:05

CommunityBot

11 silver badge

answered Dec 16, 2014 at 19:12

inspectorG4dget

115k30 gold badges159 silver badges253 bronze badges

3 Comments

njzk2 Over a year ago

yield would be nicer than print, as it would allow to use the output.

njzk2 Over a year ago

I am trying as well, no luck so far. I'll let you know when I get there.

njzk2 Over a year ago

this stackoverflow.com/a/6755918/671543 explains that before python 3, we need to re-iterate to transmit the yield, but in python 3 we can use yield from, which yields successively all items. python2 -> yield sofar + for value in allPerms(L[1:], sofar+char): yield value, python3 -> yield sofar + yield from allPerms(L[1:], sofar+char)

srj · Accepted Answer · 2014-12-16 19:03:41Z

-4

you could use the itertools module to create the permutations of your desired length. combine all the workds to one string and use it in the permutations function

lst = ['TO', 'G', 'ZDO', 'DEO', 'SGT', 'D', 'Z', 'FT', 'OV']
length = len(lst)

combined = ''.join(lst)
all_perms = itertools.permutations(combined, length)
#this will give you something like [('T', 'O', ...), (...),]

print ([''.join(x) for x in all_perms])

answered Dec 16, 2014 at 19:03

srj

10.2k2 gold badges25 silver badges28 bronze badges

5 Comments

njzk2 Over a year ago

I don't think permutations is appropriate here

CCKx Over a year ago

please explain why not

Blorgbeard Over a year ago

Did you run this code? Did you compare the output to OP's requested output?

njzk2 Over a year ago

@CCKx because it does not yield the expected output, for starters.

srj Over a year ago

@njzk2, agreed.I did not read OP's reply to the comment by Tim Castelijns. itertools.product makes much more sense.

Collectives™ on Stack Overflow

With variable length list of variable length strings, how do I create all combinations

3 Answers 3

1 Comment

3 Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

3 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related