Вы можете использовать itertools 'комбинации_with_replacement для генерации числовой части слияния.Затем замените плюсы на каждый номер в каждой комбинации:
permutatedwords = ["+me+you+", "+you+me+"]
permutatednums = ["1", "2", "12", "21"]
from itertools import combinations_with_replacement as combinationsR
wordsAndNums = [ (word,numbers) for word in permutatedwords for numbers in combinationsR(permutatednums,word.count("+")) ]
result = [ "".join(a+b for a,b in zip(word.split("+")+[""],nums)) for word,nums in wordsAndNums]
print(result)
['1me1you1', '1me1you2', '1me1you12', '1me1you21', '1me2you2',
'1me2you12', '1me2you21', '1me12you12', '1me12you21', '1me21you21',
'2me2you2', '2me2you12', '2me2you21', '2me12you12', '2me12you21',
'2me21you21', '12me12you12', '12me12you21', '12me21you21', '21me21you21',
'1you1me1', '1you1me2', '1you1me12', '1you1me21', '1you2me2', '1you2me12',
'1you2me21', '1you12me12', '1you12me21', '1you21me21', '2you2me2',
'2you2me12', '2you2me21', '2you12me12', '2you12me21', '2you21me21',
'12you12me12', '12you12me21', '12you21me21', '21you21me21']