Permutation method generating results arbitrarily

Question

I am using the permutations() function from the itertools module. I have to compare two strings. The strings can be considered equal as long as one is a permutation of the other.

The documentation for itertools.permutations() says:

itertools.permutations(iterable[, r])

Return successive r length permutations of elements in the iterable.

If r is not specified or is None, then r defaults to the length of the iterable and all possible full-length permutations are generated.

This is my code:

import itertools
mystr = []
for i in range(0, 2):
    mystr.append(input())

plist = itertools.permutations(mystr[0])
for i in plist:
    print(i)
if any(x == mystr[1] for x in plist):
    print("Yes")
else:
    print("No")

But generating plist takes too long. And when I try to print elements of plist, the process eventually gets killed because it is making too many permutations. But it should make only the permutations of length of the string itself.

My inputs are:

Dcoderplatform
patlodercDmfro

I am expecting the output to be Yes. But I get the opposite output (No).

How can I improve my algorithm?

Answer 1

Even if you only generate permutations that are the same length as the input string, the number of permutations can be very large. Consider the string in your example: Dcoderplatform. The number of permutations is the factorial of the length of the string. In this case 14! or 87178291200 permutations. So you can expect your process to be terminated when given an input string of any significant length.

Fortunately, there's an easier way to do this. Assuming you aren't required to use the permutations() function, you should use the following method.

Given two strings, str1 and str2, you can check if one is a permutation (an anagram) of the other like this:

str1 = 'Dcoderplatform'
str2 = 'patlodercDmfro'
if ''.join(sorted(str1)) == ''.join(sorted(str2)):
    print('{} and {} are anagrams'.format(str1, str2))