finding cartesian product of a set n times (itertools.product function)

Question

Hello, I was trying to find all the permutations of a set of length n, where all elements can be repeated any number of times, so basically a Cartesian product of set n times, where n is the length of the permutation.

Now I know python itertools.product can do the same easily but I wanted to do it on my own and I wrote this code
```
def gen_perm(chars,lenn):
if lenn == 1:
for i in chars:
yield i
else:
perms = gen_perm(chars,lenn-1)
for i in perms:
for j in chars:
yield i+j
```
Now I cant think of anything better than this and I feel this is not very efficient as I have to calculate all the permutations of the previous iteration i.e. n-1 length, is there any way to make it more efficient and how do python itertools does it?

Answer 1

You can get an idea of how itertools does it here (it's probably not exactly the source code, but the core idea is probably this): https://docs.python.org/3/library/itertools.html#itertools.product

It may look a little puzzling, but it's essentially just a non-recursive version of what you've done. Complexity-wise, both codes are O(size(chars) ^ lenn), which is the best you can hope for. You're yielding each result exactly once, and there aren't any major redundant steps.

So congratulations! 😊

Answer 2

Kishalaya Saha Thank you for your answer, the code you mentioned was tricky but i was able to follow through it with pen and paper:) though i assumed `[x+[y] for x in result for y in pool]`
is a nested for loop of y inside x, am i right?
Also if I want to use the intermediate values generated by the above function, i.e. for lenn-1. How can i do that from this function only without having to calculate them again?

Answer 3

Yes, you got it absolutely right! It is a list comprehension with nested for loop. You even got the order perfectly: it's y inside x, and not x inside y. Easy experiment: try
print([x+y for x in "abc" for y in "123])

I'm not sure what you mean by "use" the intermediate values, but if you just want to yield them too, you could try modifying your code like

perms = gen_perm(chars,lenn-1)
for i in perms:
yield i
if len(i) == lenn-1:
for j in chars:
yield i+j

I needed to use the if statement there to avoid duplicates: I only want to extend the i's that have length lenn-1, as the shorter ones have been dealt with in the previous turn.

But let me know if you're looking for something else 😊