Print permutation tree python3

Question

I have list of numbers and I need to create tree and print all permutations, e.g. for [1, 2, 3] it should print
123 132 213 231 312 321
Currently my code prints first element only once:
123 32 213 31 312 21
How do I fix it?

    class Node(object):
    def __init__(self):
        self.children = None
        self.data = None
        self.depth = None


class PermutationTree(object):
    def __init__(self, numbers):
        numbers = list(set(numbers))
        numbers.sort()
        self.depth = len(numbers)
        self.tree = self.generate_root(numbers)
        self.create_tree(numbers, self.tree.children,  1)

    def generate_root(self, numbers):
        root = Node()
        root.children = []
        root.depth = 0
        for i in numbers:
            tree = Node()
            tree.data = i
            tree.depth = 1
            root.children.append(tree)
        return root

    def create_tree(self, numbers, children, depth):
        depth += 1
        if depth == self.depth + 1:
            return
        for child in children:
            reduced_numbers = list(numbers)
            reduced_numbers.remove(child.data)
            child.children = []
            for j in reduced_numbers:
                tree = Node()
                tree.data = j
                tree.depth = depth
                child.children.append(tree)
            self.create_tree(reduced_numbers, child.children, depth)

    def print_tree(self):
        self.print(self.tree)

    def print(self, node):
        for i in node.children:
            print(i.data, end="")
            if not i.depth == self.depth:
                self.print(i)
                print("")

test = [1, 2, 3]
permutation_tree = PermutationTree(test)
permutation_tree.print_tree()

score 1 · Accepted Answer · edited Jun 20 '20 at 09:12

This is pretty good example showing why side effects should be done in as few places as possible.

Side effects everywhere

Your approach is like this: "I will print one digit every time it is needed." This approach gives you limited control over side effects. Your code prints many times in different recursion depths and it's hard to keep track of what is going on.

Side effects in as few places as possible

Another approach to this problem is creating side effects in one place. "I will generate all permutations first and then print them." Such a code is easier to debug and can give you better control of what is going on in your code.

If you write your code like this:

def print_tree(self): # this function takes care about printing
    for path in self.generate_path(self.tree):
        print(path)



def generate_perm(self, node): #this function takes care about generating permutations
    if not node.children: 
        return [str(node.data)]
    app_str = str(node.data) if node.data else ""
    res= []
    for child in node.children:
        for semi_path in self.generate_perm(child):
            res.append (app_str + semi_path)
    return res

P.S. generate_perm can be rewritten to be more efficient with yields.

Print permutation tree python3

1 Answers1

Side effects everywhere

Side effects in as few places as possible