Python backtracking strings lenght n from alphabet {a,b,c} with #a=#b

Question

i want to make an algoritm that finds for a given n the strings made on the alphabet {a,b,c} in which the number 'a' appears the same times of 'b'

i came out with this

n=3 #length String
h=-1 #length prefix
L=['a','b','c'] #alphabet
S=['','','',''] #solution
par=0 # it's zero if a and b have same occurence


def P(n,h,par,L,S):
    if h==n:
        if par==0:
            print(S)
    else:
        for i in L:
            if i=='a':
                par+=1
            if i=='b':
                par-=1
            S[h+1]=i
            P(n,h+1,par,L,S)
            #Update the stack after recursion
            if S[h+1]=='a':
                par-=1
            if S[h+1]=='b':
                par+=1


P(n,h,par,L,S)

i apologize for the poor string implementation but it works and it's only for studying purpose, the question is: there are ways to avoid some work for the algorithm? because it only checks #a and #b in the end after have generate all n-length strings for this alphabet. my goal is to achieve O(n*(number of strings to print))

Answer 1

You can cut out the wasted work by changing the following:

        if i=='a':
            par+=1
        if i=='b':
            par-=1

to

        oldpar = par
        if i=='a':
            par+=1
        if i=='b':
            par-=1
        # there are n-h-1 characters left to place
        # and we need to place at least abs(par) characters to reach par=0
        if abs(par)>n-h-1:
            par = oldpar
            continue

Answer 2

Is this what you're trying to do:

from itertools import combinations_with_replacement

alphabet = "abc"

def combs(alphabet, r):
    for comb in combinations_with_replacement(alphabet, r):
        if comb.count('a') == comb.count('b'):
           yield comb

For this,

list(combs(alphabet, 3)) == [('a', 'b', 'c'), ('c', 'c', 'c')]

and

list(combs(alphabet, 4)) == [('a', 'a', 'b', 'b'), 
                             ('a', 'b', 'c', 'c'), 
                             ('c', 'c', 'c', 'c')]

This will produce all combinations and reject some; according to the docs for combinations_with_replacement:

The number of items returned is (n+r-1)! / r! / (n-1)! when n > 0.

where n == len(alphabet).