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
def combo(list, size):
if size == 0 or not list: # order doesn't matter
return [list[:0]] # xyz == yzx
else:
result = []
for i in range(0, (len(list) - size) + 1): # iff enough left
pick = list[i:i+1]
rest = list[i+1:] # drop [:i] part
for x in combo(rest, size - 1):
result.append(pick + x)
return result
All three of these functions work on any sequence object that supports len, slicing, and
concatenation operations. For instance, we can use permute on instances of some of the
stack classes defined at the start of this chapter (experiment with this on your own for
more insights).
The following session shows our sequence shufflers in action. Permuting a list enables
us to find all the ways the items can be arranged. For instance, for a four-item list, there
are 24 possible permutations (4 × 3 × 2 × 1). After picking one of the four for the first
position, there are only three left to choose from for the second, and so on. Order
matters: [1,2,3] is not the same as [1,3,2], so both appear in the result:
C:\...\PP4E\Dstruct\Classics> python
>>> from permcomb import *
>>> permute([1, 2, 3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> permute('abc')
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
>>> permute('help')
['help', 'hepl', 'hlep', 'hlpe', 'hpel', 'hple', 'ehlp', 'ehpl', 'elhp', 'elph',
'ephl', 'eplh', 'lhep', 'lhpe', 'lehp', 'leph', 'lphe', 'lpeh', 'phel', 'phle',
'pehl', 'pelh', 'plhe', 'pleh']combo results are related to permutations, but a fixed-length constraint is put on the
result, and order doesn’t matter: abc is the same as acb, so only one is added to the
result set:
>>> combo([1, 2, 3], 3)
[[1, 2, 3]]
>>> combo('abc', 3)
['abc']
>>> combo('abc', 2)
['ab', 'ac', 'bc']
>>> combo('abc', 4)
[]
>>> combo((1, 2, 3, 4), 3)1396 | Chapter 18: Data Structures