Permutations to compare two different string to match

I'm cracking my head here to solve this problem.

I'm trying to compare two strings like:

a = 'apple'
b = 'ppale'

If I user permutation method, variable b could be re-generated and it can match with the variable a.

I wrote the code, god knows why, I'm only getting False value even when I'm expecting True.

import itertools

def gen(char, phrase):
    char = list(char)

    wordsList = list(map(''.join, itertools.permutations(char)))
    for word in wordsList:
        if word == phrase:
            return True
        else:
            return False

print(gen('apple', 'appel')) # should be True
print(gen('apple', 'elppa')) # should be True
print(gen('apple', 'ap')) # should be False

Solution

The problem is you're returning on the first iteration of the loop, regardless of whether there's a match or not. In particular, you're returning False the first time there's a mismatch. Instead, you need to complete the entire loop before returning False:

def gen(char, phrase):
    char = list(char)

    wordsList = list(map(''.join, itertools.permutations(char)))
    for word in wordsList:
        if word == phrase:
            return True
    return False

Note that there are some improvements that can be made. One is there's no need to do char = list(char), since char is already an iterable. Also, there's no need to expand the map result into a list. It's just being used as an iterable, so it can be used directly, which can potentially save a lot of memory:

def gen(char, phrase):
    wordsIter = map(''.join, itertools.permutations(char))
    for word in wordsIter:
        if word == phrase:
            return True
    return False

However, since you're just comparing two words for the same characters, you don't really need to generate all the permutations. Instead, you just need to check to see of the two sets of characters are the same (allowing for multiple instances of characters, so technically you want to compare two multisets). You can do this much more efficiently as follows:

import collections

def gen(char, phrase):
    counter1 = collections.Counter(char)
    counter2 = collections.Counter(phrase)
    return counter1 == counter2

This is an O(n) algorithm, which is the best that can be done for this problem. This is much faster than generating the permutations. For long strings, it's also significantly faster than sorting the letters and comparing the sorted results, which is O(n*log(n)).

Example output:

>>> gen("apple", "elxpa")
False
>>> gen("apple", "elppa")
True
>>> gen("apple", "elpa")
False
>>>

Note that this only returns True if the letters are the same, and the number of each letter is the same.

If you want to speed up the case where the two strings have different lengths, you could add a fast check up front that returns False if the lengths differ, before counting the characters.