Word Permutations

wordPermutations

"""

  Given String "ABC", print all 3-letter permutations of this
  
"""

# SOLUTION:  - FULL decision tree
#            - each level is character place, 
#              each branch a choice of one char
#            - REMAINING unchosen characters
#            eg for length 3; and set of 3 chars; have 3x2x1 order-specific ways
#            - each LEAF on decision tree corresponds to a full 3-letter permutation
# GOTCHA  :  - building and remaining are MUTABLE that get modified ACROSS stack calls
#            - remaining gets SHRUNK within each sub-recursion, and building EXPANDs
#              SO need List in Python or StringBuffer in Java
#             - AND, need to MANUALLY BACKOUT incremental at END of recursion to simulate
#              BACKTRACK on decision-tree!

# ATTN:  LOGGING EXCEPTIONs
import logging
import traceback

def rPermutations(building, remaining):
    
      # print("ENTRY:  {}, {}".format(building, remaining))
      
      # ATTN:  we have more permutations to do, ie chars remaining
      # - iterate through remaining characters to build with as branching decision!
      # CAREFUL that remaining passed to next level DOWN
      # - is just minus the ONE chosen char 
      # ie A,BC; B,AC; C, AB
      numRemainForLevel = len(remaining)
      for i in range(0,numRemainForLevel):
        
        # INCREMENT STATE prior to deeper recursion
        building.append(remaining[i])
        # GOTCHA:  take COPY of ORIG remaining MINUS aChar 
        #          to NOT SELF-MODIFY remaining while in loop dependent on original 
        #          elements; eg BC remain on choose A; next loop AC remains on choose B
        subsetRemain = list(remaining)
        subsetRemain.remove(remaining[i])
        
        # ATTN:  GATE condition before further DEPTH recursion with subset remaining!
        # but continue BREADTH looping with original remaining!
        if subsetRemain:
          rPermutations(building, subsetRemain)
        # ATTN:  detect LEAF condition to print results!
        else:
          # ATTN:  convert MUTABLE BACK to IMMUTABLE String!
          print('FOUND LEAF PERMUTATION:  ')
          print(''.join(building))
          print(', ')
        
        # GOTCHA:  BACKOUT to reset subset remaining for NEXT LOOP iteration in SAME
        # RECURSE LEVEL!
        building.pop()
          
      # default return to EXIT recursion at ANY DEPTH LEVEL after finishing BREADTH LOOP
      # print('DEFAULT EXIT RECURSION')

  
# TEST DRIVER
try:
  
  test1 = "A"
  # rPermutations(list(""), list(test1))
  
  test2 = "AB"
  # rPermutations(list(""), list(test2))
  
  test3 = "ABC"
  rPermutations(list(""), list(test3))
  
  test4 = ""
  # rPermutations(list(""), list(test4))

except Exception as ex:

  print (traceback.format_exc())
  
  # print(ex)
  # TODO:  repl.it doesn't show this in output!
  # logging.exception(ex)