simple recursion help

Steven Bethard steven.bethard at gmail.com
Sat Oct 23 22:30:02 CEST 2004


drs <drs <at> remove-to-send-mail-ecpsoftware.com> writes:

> I am looking for a list of all unique strings of length x whose
> elements are from the set a, b, and c.
> 
> So, for example, in this case it would be
> 
> aaa, aab, aac, aba, abb, abc, aca, acb, acc, ... cca, ccb, ccc
> 
> but I need for the length and the number of elements to be variable.


Much clearer, thanks.  Is this what you're looking for:

>>> def f(chars, n):
... 	for char in chars:
... 		if n == 1:
... 			yield char
... 		else:
... 			for string in f(chars, n-1):
... 				yield char + string
... 				
>>> list(f('abc', 1))
['a', 'b', 'c']
>>> list(f('abc', 2))
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
>>> list(f('abc', 3))
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab',
'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba',
'cbb', 'cbc', 'cca', 'ccb', 'ccc']

Steve




More information about the Python-list mailing list