This test finds three paths in its graph between nodes S and M. We’ve really only
scratched the surface of this academic yet useful domain here; experiment further on
your own, and see other books for additional topics (e.g., breadth-first search by levels,
and best-first search by path or state scores):
C:\...\PP4E\Dstruct\Classics> python gtestobj2.py
[[s, m], [s, p, m], [s, p, a, m]]Permuting Sequences
Our next data structure topic implements extended functionality for sequences that is
not present in Python’s built-in objects. The functions defined in Example 18-22 shuffle
sequences in a number of ways:
permute
constructs a list with all valid permutations of any sequence
subset
constructs a list with all valid permutations of a specific length
combo
works like subset, but order doesn’t matter: permutations of the same items are
filtered out
These results are useful in a variety of algorithms: searches, statistical analysis, and
more. For instance, one way to find an optimal ordering for items is to put them in a
list, generate all possible permutations, and simply test each one in turn. All three of
the functions make use of generic sequence slicing so that the result list contains se-
quences of the same type as the one passed in (e.g., when we permute a string, we get
back a list of strings).
Example 18-22. PP4E\Dstruct\Classics\permcomb.py
"permutation-type operations for sequences"
def permute(list):
if not list: # shuffle any sequence
return [list] # empty sequence
else:
res = []
for i in range(len(list)):
rest = list[:i] + list[i+1:] # delete current node
for x in permute(rest): # permute the others
res.append(list[i:i+1] + x) # add node at front
return res
def subset(list, size):
if size == 0 or not list: # order matters here
return [list[:0]] # an empty sequence
else:
result = []
Permuting Sequences | 1395