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: 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`](http://docs.python.org/2/library/itertools.html#itertools.combinations_with_replacement):

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

where `n == len(alphabet)`.

