Question

• Develop Python implementation of combinatorial algorithm which will find all possible Anagrams of user input. Hint: use backtracking algorithm.
• Example:
• Input = ROWAN UNIVERSITY
• Output (298 possibilities):
• YOUR WINTERS VAIN
• OAT RUINS WIN VERY
• …
• ROAR TUNES WIN IVY
• IRONY UNWISER VAT
• TIE IN SUN ROW VARY…

Answer 1

Anagram : It is a string which can be formed rearranging characters of the string.

Approach :

1.For each element at i we will swap it with all other elements after if it doesnot contain duplicates.

We will reswap for every element after index i and backtract it.

Below is implementation of above approach :

def single_occur(s, start, curr): 
    for i in range(start, curr): 
        if s[i] == s[curr]: 
            return 0
    return 1
# Store all anagrams
anagrams=[]

def findPermutations(cur_string, index, n): 
    if index == n: 
        s=""
        for i in cur_string:
            s+=i
        anagrams.append(s)
        return
 
    for i in range(index, n): 
        # Proceed further for str[i] if and only if 
        # occur only one time in between s[index] and s[i]
        # if it occur only one time swap index with i
        # and recur and then swap them again to backtrack
        check = single_occur(cur_string, index, i) 
        if check: 
            temp = cur_string[index]
            cur_string[index]=cur_string[i]
            cur_string[i]=temp
            findPermutations(cur_string, index + 1, n)
            temp = cur_string[index]
            cur_string[index]=cur_string[i]
            cur_string[i]=temp  
string = list(input())
n = len(string)
findPermutations(string, 0, n)
cnt=len(anagrams)
print("Total anagrams =",cnt)
for i in anagrams:
    print(''.join(i))

Below is screenshot of code along with output