about summary refs log tree commit diff
path: root/data_structures_and_algorithms/permutations.py
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-01-29T14·43+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-01-29T14·43+0000
commit5c9079a41059e077f2b71b68eb83ff9fcb2e38d1 (patch)
treedce7e3566b04213228fb3c92fc593ca18841d972 /data_structures_and_algorithms/permutations.py
parentfb9380ba268b3cd27372acadb87b14cc96163374 (diff)
Splice ./universe directory into ./
Manually merging:
- README.md: I added the description from universe/README.md into the heading of
  dotfiles/README.md.
- .envrc: dotfiles/.envrc was a superset of universe/.envrc
- .gitignore: Adding some of the ignored patterns from universe/.gitignore to
  dotfiles/.gitignore

Everything else here should be a simple rename.
Diffstat (limited to 'data_structures_and_algorithms/permutations.py')
-rw-r--r--data_structures_and_algorithms/permutations.py55
1 files changed, 55 insertions, 0 deletions
diff --git a/data_structures_and_algorithms/permutations.py b/data_structures_and_algorithms/permutations.py
new file mode 100644
index 000000000000..fc2c1ef7eebc
--- /dev/null
+++ b/data_structures_and_algorithms/permutations.py
@@ -0,0 +1,55 @@
+class Node(object):
+    # ctor :: a -> [a] -> Node(a)
+    def __init__(self, value, children=[]):
+        self.value = value
+        self.children = children
+
+
+# is_leaf :: Node(a) -> Boolean
+def is_leaf(node):
+    return len(node.children) == 0
+
+
+# enumerate :: Node(a) -> Set(List(a))
+def enumerate(node):
+    current = []
+    result = []
+    q = []
+
+    q.append(node)
+
+    while q:
+        x = q.pop()
+        print(x.value)
+
+        for c in x.children:
+            q.append(c)
+
+        current.append(x.value)
+        print(current)
+
+        if is_leaf(x):
+            result.append(current)
+            print("Reseting current")
+            current = []
+
+    return result
+
+
+node = Node('root', [
+    Node('a', [
+        Node('b', [Node('c')]),
+        Node('c', [Node('b')]),
+    ]),
+    Node('b', [
+        Node('a', [Node('c')]),
+        Node('c', [Node('a')]),
+    ]),
+    Node('c', [
+        Node('a', [Node('b')]),
+        Node('b', [Node('a')]),
+    ])
+])
+
+print('----------')
+print(enumerate(node))