Given a string, prints out all possible permutations using a Trie. Solutions for both with and without duplicate characters. Implemented in python.

perm_trie.py

__author__ = 'shawli'

#no duplicates

class Trie:

    def __init__(self, ch=""):
        self.ch = ch #character
        self.br = [] #branches

    def addToBranch(self, x):
        self.br.append(x)

    def setChar(self, c):
        self.ch = c

    def makeTrie(self, s):

        if not s:
            return

        if len(s) == 1:
            newTrie = Trie(s)
            self.addToBranch(newTrie)
            return self

        for i in range(len(s)):
            newTrie = Trie(s[i])
            rest = s[:i] + s[i+1:]
            self.addToBranch(newTrie)
            self.br[-1].makeTrie(rest)

    def allPerm(self):
        perms = []
        if not self.br:
            return [self.ch]
        for i in self.br:
            for j in i.allPerm():
                perms.append(self.ch + j)
        return perms

x = Trie()
x.makeTrie("abc")
print x.allPerm()
print len(x.allPerm())

# > ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
# > 6

perm_trie_dups.py

__author__ = 'shawli'

#duplicates allowed

class Trie:

    def __init__(self, ch=""):
        self.ch = ch #character
        self.br = [] #branches

    def addToBranch(self, x):
        self.br.append(x)

    def setChar(self, c):
        self.ch = c

    def makeTrie(self, s):

        if not s:
            return

        "".join(sorted(s))

        if len(s) == 1:
            newTrie = Trie(s)
            self.setChar(newTrie)
            return self

        for i in range(len(s)):
            if (i == 0) or (s[i-1] is not s[i]):
                newTrie = Trie(s[i])
                rest = s[:i] + s[i+1:]
                self.addToBranch(newTrie)
                self.br[-1].makeTrie(rest)

    def allPerm(self):
        perms = []
        if not self.br:
            return [self.ch]
        for i in self.br:
            for j in i.allPerm():
                perms.append(self.ch + j)
        return perms

x = Trie()
x.makeTrie("abb")
print x.allPerm()
print len(x.allPerm())

# > ['abb', 'bab', 'bba']
# > 3