Python3 permutation based on Tree Structure

Question

I am trying to used the Tree Structure for creating a permutation function:

import copy
def myPermutation (newString, newDict):
    if sum(newDict.values()) == 0:
    return ' '
else:
    curDict = copy.deepcopy(newDict)
    nextDict = copy.deepcopy(newDict)
    results = []

    for i in range(len(newString)):
        curChar = newString[i]
        if curDict[curChar] == 0:
            continue
        else:
            print(curDict, ' -> ', curChar)
            nextDict[curChar] -= 1
            print(nextDict)
            for p in myPermutation(newString, nextDict):
                results.append(curChar+p)
            # myPermutation(newString, nextDict)
            # results.append(curChar)
            nextDict=copy.deepcopy(newDict)
    return results

def curDict (newString):
    myDict = dict()
    for char in newString:
        myDict[char] = myDict.get(char,0) + 1
    return myDict

newString = 'ABC'
newDict = curDict(newString)
test = myPermutation(newString, newDict)
print(test)

The output is like this: ['ABC ', 'ACB ', 'BAC ', 'BCA ', 'CAB ', 'CBA ']

But if I used 'AAB' as test data my output is: ['AAB ', 'AAB ', 'ABA ', 'ABA ', 'AAB ', 'AAB ', 'ABA ', 'ABA ', 'BAA ', 'BAA ', 'BAA ', 'BAA ']

The whole purpose for using tree structure to do permutation is if one of the char is duplicate, I can avoid overloading recursion function. click here for "tree structure algorithm"

1. Any one has idea for adjusting the code to make the algorithm works?
2. How to avoid using return ' ' in permutation function? According to my output, every permutation element has a SPACE. I tried to use '' or None, but the complier always give me error message.

Answer 1

for SPACE issue, I can simply use:

for items in test:
print(items.strip(), end=' ')

but, is there anyway I can directly do inside permutation function?

Answer 2

Ok, I figured it out, according to the algorithm, I need convert 'inputString' to a distinct Char String, which convert 'AAB' to 'AB' Then pass the distinct Char String with dict into the permutation function. Here is the new code:

import copy

def myPermutation (newString, newDict):
    if sum(newDict.values()) == 0:
        return ' '
else:
    curDict = copy.deepcopy(newDict)
    nextDict = copy.deepcopy(newDict)
    results = []

    for curChar in newString:
        if curDict[curChar] == 0:
            continue
        else:
            nextDict[curChar] -= 1
            for p in myPermutation(newString, nextDict):
                results.append(curChar+p)
            nextDict=copy.deepcopy(newDict)
    return results

def curDict (newString):
    myDict = dict()
    for char in newString:
        myDict[char] = myDict.get(char,0) + 1
    return myDict

def myDistStr(newDict):
    myStr = ''
    for k, v in newDict.items():
        myStr = k+myStr
    return myStr

newString = 'AABBC'
newDict = curDict(newString)
test = myPermutation(myDistStr(newDict), newDict)
print(len(test))
print(test)