Welcome, guest | Sign In | My Account | Store | Cart

Generating all strings of some length of a given alphabet (Python recipe) by Yuce Tekol
ActiveState Code (http://code.activestate.com/recipes/425303/)

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, 19 lines
Download
 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

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

Tags: algorithms

4 comments

Raymond Hettinger 18 years, 10 months ago  # | flag

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
Yuce Tekol (author) 18 years, 10 months ago  # | flag

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
Yuce Tekol (author) 18 years, 10 months ago  # | flag

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

joran 9 years, 1 month ago  # | flag 
allstrings=itertools.permutations

there thats the easiest

Created by Yuce Tekol on Thu, 9 Jun 2005 (PSF)
◄ Python recipes (4591) ►
◄ Yuce Tekol's recipes (1) ►

Required Modules

  • (none specified)

Other Information and Tasks