You are previewing Programming Python, 4th Edition.

# 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 sequences 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 = [] for i in range(len(list)): pick = list[i:i+1] # sequence slice rest = list[:i] ...`