Skip to content

Instantly share code, notes, and snippets.

@tahia-khan tahia-khan/perm_trie.py
Last active Aug 29, 2015

Embed
What would you like to do?
Given a string, prints out all possible permutations using a Trie. Solutions for both with and without duplicate characters. Implemented in python.
__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
__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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.