Find all list permutations of splitting a string in Python
The idea is to realize that the permutation of a string s
is equal to a set containing s
itself, and a set union of each substring X
of s
with the permutation of s\X
. For example, permute('key')
:
{'key'} # 'key' itself
{'k', 'ey'} # substring 'k' union 1st permutation of 'ey' = {'e, 'y'}
{'k', 'e', 'y'} # substring 'k' union 2nd permutation of 'ey' = {'ey'}
{'ke', 'y'} # substring 'ke' union 1st and only permutation of 'y' = {'y'}
- Union of 1, 2, 3, and 4, yield all permutations of the string
key
.
With this in mind, a simple algorithm can be implemented:
>>> def permute(s):
result = [[s]]
for i in range(1, len(s)):
first = [s[:i]]
rest = s[i:]
for p in permute(rest):
result.append(first + p)
return result
>>> for p in permute('monkey'):
print(p)
['monkey']
['m', 'onkey']
['m', 'o', 'nkey']
['m', 'o', 'n', 'key']
['m', 'o', 'n', 'k', 'ey']
['m', 'o', 'n', 'k', 'e', 'y']
['m', 'o', 'n', 'ke', 'y']
['m', 'o', 'nk', 'ey']
['m', 'o', 'nk', 'e', 'y']
['m', 'o', 'nke', 'y']
['m', 'on', 'key']
['m', 'on', 'k', 'ey']
['m', 'on', 'k', 'e', 'y']
['m', 'on', 'ke', 'y']
['m', 'onk', 'ey']
['m', 'onk', 'e', 'y']
['m', 'onke', 'y']
['mo', 'nkey']
['mo', 'n', 'key']
['mo', 'n', 'k', 'ey']
['mo', 'n', 'k', 'e', 'y']
['mo', 'n', 'ke', 'y']
['mo', 'nk', 'ey']
['mo', 'nk', 'e', 'y']
['mo', 'nke', 'y']
['mon', 'key']
['mon', 'k', 'ey']
['mon', 'k', 'e', 'y']
['mon', 'ke', 'y']
['monk', 'ey']
['monk', 'e', 'y']
['monke', 'y']
Consider more_itertools.partitions
:
Given
import more_itertools as mit
s = "monkey"
Demo
As-is:
list(mit.partitions(s))
#[[['m', 'o', 'n', 'k', 'e', 'y']],
# [['m'], ['o', 'n', 'k', 'e', 'y']],
# [['m', 'o'], ['n', 'k', 'e', 'y']],
# [['m', 'o', 'n'], ['k', 'e', 'y']],
# [['m', 'o', 'n', 'k'], ['e', 'y']],
# [['m', 'o', 'n', 'k', 'e'], ['y']],
# ...]
After some string joining:
[list(map("".join, x)) for x in mit.partitions(s)]
Output
[['monkey'],
['m', 'onkey'],
['mo', 'nkey'],
['mon', 'key'],
['monk', 'ey'],
['monke', 'y'],
['m', 'o', 'nkey'],
['m', 'on', 'key'],
['m', 'onk', 'ey'],
['m', 'onke', 'y'],
['mo', 'n', 'key'],
['mo', 'nk', 'ey'],
['mo', 'nke', 'y'],
['mon', 'k', 'ey'],
['mon', 'ke', 'y'],
['monk', 'e', 'y'],
['m', 'o', 'n', 'key'],
['m', 'o', 'nk', 'ey'],
['m', 'o', 'nke', 'y'],
['m', 'on', 'k', 'ey'],
['m', 'on', 'ke', 'y'],
['m', 'onk', 'e', 'y'],
['mo', 'n', 'k', 'ey'],
['mo', 'n', 'ke', 'y'],
['mo', 'nk', 'e', 'y'],
['mon', 'k', 'e', 'y'],
['m', 'o', 'n', 'k', 'ey'],
['m', 'o', 'n', 'ke', 'y'],
['m', 'o', 'nk', 'e', 'y'],
['m', 'on', 'k', 'e', 'y'],
['mo', 'n', 'k', 'e', 'y'],
['m', 'o', 'n', 'k', 'e', 'y']]
Install via > pip install more_itertools
.
http://wordaligned.org/articles/partitioning-with-python contains an interesting post about sequence partitioning, here is the implementation they use:
#!/usr/bin/env python
# From http://wordaligned.org/articles/partitioning-with-python
from itertools import chain, combinations
def sliceable(xs):
'''Return a sliceable version of the iterable xs.'''
try:
xs[:0]
return xs
except TypeError:
return tuple(xs)
def partition(iterable):
s = sliceable(iterable)
n = len(s)
b, mid, e = [0], list(range(1, n)), [n]
getslice = s.__getitem__
splits = (d for i in range(n) for d in combinations(mid, i))
return [[s[sl] for sl in map(slice, chain(b, d), chain(d, e))]
for d in splits]
if __name__ == '__main__':
s = "monkey"
for i in partition(s):
print i
Which would print:
['monkey']
['m', 'onkey']
['mo', 'nkey']
['mon', 'key']
['monk', 'ey']
['monke', 'y']
['m', 'o', 'nkey']
['m', 'on', 'key']
['m', 'onk', 'ey']
['m', 'onke', 'y']
['mo', 'n', 'key']
['mo', 'nk', 'ey']
['mo', 'nke', 'y']
['mon', 'k', 'ey']
['mon', 'ke', 'y']
['monk', 'e', 'y']
...
['mo', 'n', 'k', 'e', 'y']
['m', 'o', 'n', 'k', 'e', 'y']
def splitter(str):
for i in range(1, len(str)):
start = str[0:i]
end = str[i:]
yield (start, end)
for split in splitter(end):
result = [start]
result.extend(split)
yield result
combinations = list(splitter(str))
Note that I defaulted to a generator to save you from running out of memory with long strings.