Вы можете использовать рекурсию с генератором:
from collections import Counter
def combo(d, c = []):
if len(c) == len(d):
yield ''.join(c)
else:
_c1, _c2 = Counter(d), Counter(c)
for i in d:
if _c2.get(i, 0) < _c1[i]:
yield from combo(d, c+[i])
word = 'aan'
print(list(set(combo(word))))
Выход:
['aan', 'naa', 'ana']
word = 'ain'
print(list(set(combo(word))))
Выход:
['ina', 'nia', 'nai', 'ani', 'ian', 'ain']