CODEWITHSUNDEEP
pythonstringrecursionpermutation
Heber Alvarez
Heber Alvarez

Reputation: 15

How to get permutations of a string without repetition, using recursion, but without for or while loops?

I'm learning python and sorting algorithms. I want to find the permutations of this string 'AAABB', without repetition. I must get to the answer without using for nor while loops, only recursion.

I believe this problem can be solved generating three possible cases.

  1. Will always return A if available

  2. Will always return B if available and

  3. W will return nothing if there are no letters left available.

So far I have tried this code:

#n1 = Amount of A available 
#l1 = character A
#n2 = Amount of B available
#l2 = character B

def perm(n1,l1,n2,l2):
 if n1 == 0: # Run out of A?
     if n2 == 0: # Yes, no A left. Run out of B?: 
         return '\n' # Yes, no A nor B left, then do nothing
     else: # No, still have B, then:
         return l2 + perm(n1,l1,n2-1,l2) # Return B

 else: # No, still have A, then :
     if n2 == 0: # Run out of B?
         return l1 + perm(n1-1,l1,n2,l2)  # Yes, no B left, then return A
     else: # No, still have B, then:
         return l1+perm(n1-1,l1,n2,l2) + l2+perm(n1,l1,n2-1,l2) # Return both

print(perm(3,'A',2,'B'))

This code returns 10 incomplete permutations:
AAABB BAB BA BAAB BA BAA BAAAB BA BAA BAAA

I'm expecting to get 10 complete permutations:
AAABB AABBA AABAB ABBAA ABABA ABAAB BAABA BAAAB BABAA BBAAA.

Have you got any ideas of how can I improve my code or what condition I'm missing?

Upvotes: 1

Views: 225

Answers (1)

steviestickman
steviestickman

Reputation: 1251

First of there are 4 cases in your approach.

  1. n1 == 0 and n2 == 0 returns '\n'
  2. n1 >= 1 and n2 == 0 returns n1 * l1 + '\n'
  3. n1 == 0 and n2 >= 1 returns n2 * l2 + '\n'
  4. n1 >= 1 and n2 >= 1 returns l1 + perm(...) and returns l2 + perm(...)

And the problem is with the fourth case. since you use the call stack to join the string you get a partial entry back.

  1. AAABB
  2. ^^BAB
  3. ^^^BA
  4. ^BAAB
  5. ^^^BA
  6. ^^BAA
  7. BAAAB
  8. ^^^BA
  9. ^^BAA
  10. ^BAAA

the carot caracter (^) should be the caracter that is directly above it, but is missing in your permutations.

the solution is to maintain your own list of preceding caracters and add those before the trivial case (1).

    def perm(n1, l1, n2, l2, prefix=""):
        if n1 == 0 and n2 == 0:
            return prefix + '\n'
        elif n1 >= 1 and n2 >= 1:
            return perm(...) + perm(...)
        ...
        elif n1 >= 1 and n2 == 0:
            return perm(..., prefix+l1)

Upvotes: 1

Related Questions