about summary refs log tree commit diff
path: root/data_structures_and_algorithms/perm-tree.py
blob: 0eb389c26bb98a84d743a29ab7e3e4b2f7720f67 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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)