How to generate anagrams from an input string in a short and effective way?-CodePudding

Write a program to generate all potential anagrams of an input string.

For example, the potential anagrams of "biro" are

biro bior brio broi boir bori ibro ibor irbo irob iobr iorb rbio rboi ribo riob roib robi obir obri oibr oirb orbi orib

I couldn't find a specific correction to that question in the forums, so if this is a duplicate please feel free to send me to the topic I should be looking at.

I'm a beginner and I don't know enough about Python yet to use the right functions and methods for this exercise. I came up with that to test something. But it's a total mess and it fails to do the job, don't waste time deciphering it :

texte = "biro"
liste = list(texte)
n_liste = []
for itera, f in enumerate(liste) :
   if f == liste[0]:
       n_string = str(liste[itera]) str(liste[(liste.index(f) 1):])
   if f == liste[itera] and (itera >= 1):
       n_string = str(liste[0]) str(liste[liste.index(f)]) str(liste[(liste.index(f) 1):])
   if f == liste[len(liste)-1]:
       n_string = str(liste[0]) str(liste[liste.index(f):])
   n_liste.append(n_string)
print(n_liste)

The text to work on should be an input, not a str variable. Are there any efficient ways to find anagrams of a given string no matter how long it is? (without using libraries)

CodePudding user response：

You could make a recursive generator:

def anagrams(S,anagram=""):
   if not S:                    # no more characters,
      yield anagram             # return completed anagram
      return
   for i,c in enumerate(S):     # with each letter at current position
      yield from anagrams(S[:i] S[i 1:],anagram c) # add sub-anagrams

output:

for a in anagrams('biro'): print(a)
biro
bior
brio
broi
boir
bori
ibro
ibor
irbo
irob
iobr
iorb
rbio
rboi
ribo
riob
robi
roib
obir
obri
oibr
oirb
orbi
orib

This could also be achieved with an iterative approach where you start out with the original string in a list and progressively expand the list by swapping characters into each position with the characters in the remaining positions.

def anagrams(S):
    result = [S]
    for i in range(len(S)):                # position to swap into
        result,partial = [],result
        for p in partial:                  # partially expanded so far
            for j,c in enumerate(p[i:],i): # swap with each remaining
                result.append(p[:i] c p[i:j] p[j 1:])
    return result

CodePudding user response：

def anagrams(values):
    result = []

    if len(values) == 0:
        return [""]

    for first_index in range(len(values)):
        first = values[first_index]
        rest  = values[:first_index]   values[first_index 1:]
        for rest_permutation in anagrams(rest):
            result.append(first   rest_permutation)

    return result

# Example
print(anagrams("biro"))