Edit: A possible answer has been posted on SO. I need to verify it myself but it looks correct at the moment. The answer is here at: https://stackoverflow.com/a/46670077/5609349

How do I generate all possible Newick Tree permutations for a set of species given an outgroup?

For those who don't know what Newick tree format is, a good description is available at: https://en.wikipedia.org/wiki/Newick_format

I want to create all possible Newick Tree permutations for a set of species given an outgroup. The number of possible leaf nodes is either 4, 5, or 6.

Both "Soft" and "hard" polytomies are allowed. See: https://en.wikipedia.org/wiki/Polytomy#Soft_polytomies_vs._hard_polytomies https://biology.stackexchange.com/questions/23667/evidence-discussions-of-hard-polytomy

Shown below is the ideal output, with "E" set as the outgroup

Ideal Output:

((("A","B","C"),("D"),("E"));
((("A","B","D"),("C"),("E"));
((("A","C","D"),("B"),("E"));
((("B","C","D"),("A"),("E"));
((("A","B")("C","D"),("E"));
((("A","C")("B","D"),("E"));
((("B","C")("A","D"),("E"));
(("A","B","C","D"),("E"));
(((("A","B"),"C"),"D"),("E"));

However, any possible solutions that I've come with using itertools, specifically itertools.permutations, have come across the problem of equivalent output. The last idea I came up with involved the equivalent output that is shown below and I think a solution would definitely involve set.

Equivalent output:

((("C","B","A"),("D"),("E"));
((("C","A","B"),("D"),("E"));
((("A","C","B"),("D"),("E"));

Here is the start of my idea for a solution. However, I'm not really sure what to about this problem besides itertools and set for now.

import itertools

def Newick_Permutation_Generator(list_of_species, name_of_outgroup)
    permutations_list =(list(itertools.permutations(["A","B","C","D","E"])))

    for given_permutation in permutations_list:
        process(given_permutation)

Newick_Permutation_Generator(["A","B","C","D","E"], "E")