ActiveState Code

Recipe 425303: Generating all strings of some length of a given alphabet

This recipe shows a way to generate a list of all strings (in this case, string=list of symbols) of a given alphabet having a specified length; by using list comprehensions.

UPDATE: The case for alphabet length = 1 is fixed.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def allstrings(alphabet, length):
	"""Find the list of all strings of 'alphabet' of length 'length'"""
	
	if length == 0: return []
	
	c = [[a] for a in alphabet[:]]
	if length == 1: return c
	
	c = [[x,y] for x in alphabet for y in alphabet]
	if length == 2: return c
	
	for l in range(2, length):
		c = [[x]+y for x in alphabet for y in c]
		
	return c

if __name__ == "__main__":
	for p in allstrings([0,1,2],4):
		print p

Discussion

Strings (not the 'string' type) are frequently used in computer science; for example numbers are encoded as strings of base-2 numbers (having an alphabet of {0,1}). This implementation is just a quick hack; it uses cartesian product to find the stings, so it will consume a large space of memory (m**n lists of size n, where m is the size of the alphabet, and n is the desired length).

For more info. about strings: http://mathworld.wolfram.com/String.html

Comments

  1. 1. At 2:47 a.m. on 15 jun 2005, Raymond Hettinger said:

    Simplified. The special cases for length zero, one, and two can be eliminated. All the logic you need is in the final block:

    def allstrings(alphabet, length):
    """Find the list of all strings of 'alphabet' of length 'length'"""

    c = [[]]
    for i in range(length):
        c = [[x]+y for x in alphabet for y in c]
    return c
  2. 2. At 3:43 a.m. on 16 jun 2005, Yuce Tekol (the author) said:

    Thanks for the modification; but I think the function should output [] for length=1. Here is another modification to do that:

    def allstrings2(alphabet, length):
    """Find the list of all strings of 'alphabet' of length 'length'"""

    c = []
    for i in range(length):
        c = [[x]+y for x in alphabet for y in c or [[]]]

    return c
  3. 3. At 5:54 a.m. on 16 jun 2005, Yuce Tekol (the author) said:

    Sorry. It should be, "but I think the function should output [] for length=0."

Sign in to comment