about summary refs log tree commit diff
path: root/universe/data_structures_and_algorithms/perm-tree.py
diff options
context:
space:
mode:
Diffstat (limited to 'universe/data_structures_and_algorithms/perm-tree.py')
-rw-r--r--universe/data_structures_and_algorithms/perm-tree.py83
1 files changed, 0 insertions, 83 deletions
diff --git a/universe/data_structures_and_algorithms/perm-tree.py b/universe/data_structures_and_algorithms/perm-tree.py
deleted file mode 100644
index 0eb389c26bb9..000000000000
--- a/universe/data_structures_and_algorithms/perm-tree.py
+++ /dev/null
@@ -1,83 +0,0 @@
-import unittest
-
-
-################################################################################
-# Answer
-################################################################################
-class Node(object):
-    def __init__(self, value, children=set()):
-        self.value = value
-        self.children = children
-
-
-# treeify :: Char -> Set(Char) -> Node(Char)
-def treeify(x, xs):
-    return Node(x, [treeify(c, xs - {c}) for c in xs])
-
-
-# dft :: Node(Char) -> [String]
-def dft(node):
-    result = []
-    s = []
-
-    s.append(('', node))
-
-    while s:
-        p, n = s.pop()
-        p += str(n.value)
-
-        if not n.children:
-            result.append(p)
-        else:
-            for c in n.children:
-                s.append((p, c))
-
-    return result
-
-
-# main :: String -> Set(String)
-def get_permutations(xs):
-    if xs == '':
-        return set([''])
-
-    ys = set(xs)
-    trees = []
-
-    for y in ys:
-        trees.append(treeify(y, ys - {y}))
-
-    result = set()
-
-    for t in trees:
-        for d in dft(t):
-            result.add(d)
-
-    return result
-
-
-################################################################################
-# Tests
-################################################################################
-class Test(unittest.TestCase):
-    def test_empty_string(self):
-        actual = get_permutations('')
-        expected = set([''])
-        self.assertEqual(actual, expected)
-
-    def test_one_character_string(self):
-        actual = get_permutations('a')
-        expected = set(['a'])
-        self.assertEqual(actual, expected)
-
-    def test_two_character_string(self):
-        actual = get_permutations('ab')
-        expected = set(['ab', 'ba'])
-        self.assertEqual(actual, expected)
-
-    def test_three_character_string(self):
-        actual = get_permutations('abc')
-        expected = set(['abc', 'acb', 'bac', 'bca', 'cab', 'cba'])
-        self.assertEqual(actual, expected)
-
-
-unittest.main(verbosity=2)