O'Reilly logo

Programming Python, Second Edition by Mark Lutz

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Permuting Sequences

The functions defined in Example 17-23 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 the generic sequence slicing tricks of the reversal functions in the prior section, 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 17-23. PP2E\Dstruct\Classics\permcomb.py

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] + list[i+1:] # keep [:i] part for x in subset(rest, size-1): result.append(pick + x) return result ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required