Print all permutations from a given list of strings such that each set of strings is completely unique Problem : Given a list of strings, some of which may be anagrams amongst themselves, print the permutations which can be so constructed so that each permutation has set of strings which is completely unique.


input :  “asda”, “daas”, “dand”, “nadd”

output :  {“asda”, “dand”}, {“daas”, “dand”}, {“asda”, “nadd”}, {“daas”, “nadd”}


input  :  “laptop”, “toplap”, “loptap”, “mouse”

output :  {“laptop”, “mouse”}, {“toplap”, “mouse”}, {“loptap”, “mouse”}


Code :

def is_anagram(value_1, value_2):
    """checks whether the two given strings are anagrams """
    if sorted(value_1) == sorted(value_2):
        return True

def random_set(input_value):
    """returns the set of strings which are completely unique"""
    if len(input_value) &lt;= 2:
        output = input_value
    else:
        output = []
        for i in range(len(input_value)):
            for j in range(len(input_value)):
                if not is_anagram(input_value[i], input_value[j]):
                    output.append( {input_value[i], input_value[j]})

    return output

print random_set(["asda", "daas" , "dand" , "nadd"])
print random_set(["laptop", "toplap", "loptap", "mouse"])


Though the code gives the correct output but it makes duplicate copy of the sets. How can i remove this flaw?
I don't think your current algorithm is that good.


You loop through all input_values twice, not even removing clearly know duplicates.

If you instead used say a half_product function, then you'd remove a lot of checks.
This is as you know if you've already visited the value with i, then you won't need to visit again with j.

This is as set('ab') == set('ba').
You can group the anagrams, to reduce the code complexity.

Currently you have two \$O(n)\$ loops - running in \$O(n^2)\$ time - where \$n\$ is the size of input_values.
After this, you then run in \$O(v\log{v})\$ - where \$v\$ is the max size of the values.
And so is \$O(n^2 v\log{v})\$.

However you can group all the values in \$O(n v\log{v})\$ time.
This means you now have \$g\$ groups, of \$a\$ anagrams. Being roughly \$ag = n\$.
From this you have to loop all groups and anagrams leaving \$O(g^2 a^2)\$ time.
And so is \$O(n v\log{v} + g^2 a^2)\$. Which is better in all cases, except where \$g\$ or \$a\$ are \$1\$.


And so I'd use:

def half_product(it):
    it = list(it)
    for i, value in enumerate(it):
        for j in range(i+1, len(it)):
            yield value, it[j]

def random_set(values):
    d = {}
    for value in values:
        d.setdefault(tuple(sorted(value)), set()).add(value)

    for anagrams in half_product(d.values()):
        yield from itertools.product(*anagrams)