Find all permutations in a line break list in Python

Question

I have a string of letters that I would like to split into all possible combinations (the order of letters should remain fixed) so that:

s = 'monkey' 

becomes:

 combinations = [['m', 'onkey'], ['mo', 'nkey'], ['m', 'o', 'nkey'] ... etc] 

Any ideas?

Answer 1

 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)) 

Please note that I used the generator by default so that you don't run out of memory with long strings.

Answer 2

http://wordaligned.org/articles/partitioning-with-python contains an interesting post about breaking up sequences, 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 

To 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'] 

Answer 3

The idea is to understand that the permutation of the string s is equal to the set containing s itself and the union of the set of each substring X of s with the permutation 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 1, 2, 3, and 4, returns 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'] 

Answer 4

A line-oriented (as opposed to a list) approach is to think that each adjacent pair of characters is separated by a space or an empty string. This can be compared with 1 and 0, and the number of possible splits is 2:

2 ^ (len (s) -1)

for example, a “key” can have '' or '' separation of 'ke' and '' or '' separation of 'ey', which leads to 4 possibilities:

• ('' between 'k' and 'e', ​​'' between 'e' and 'y')
• k ey ('' between 'k' and 'e', ​​'' between 'e' and 'y')
• key ('' between 'k' and 'e', ​​'' between 'e' and 'y')
• ke y ('' between 'k' and 'e', ​​'' between 'e' and 'y')

Unreadable python is one liner that gives you the generator as a string:

 operator_positions = (''.join([str(a >> i & 1).replace('0', '').replace('1', ' ') + s[len(s)-1-i] for i in range(len(s)-1, -1, -1)]) for a in range(pow(2, len(s)-1))) 

A readable version of this generator with comments and a sample:

 s = 'monkey' s_length = len(s)-1 # represents the number of ' ' or '' that can split digits operator_positions = ( ''.join( [str(a >> i & 1).replace('0', '').replace('1', ' ') + s[s_length-i] for i in range(s_length, -1, -1)]) # extra digit is for blank string to always precede first digit for a in range(pow(2, s_length)) # binary number loop ) for i in operator_positions: print i 

str (a → me and 1) converts a to a binary string, which then has 0 and 1 is replaced by `` and '' respectively. The binary string is an extra digit in length, so the first digit is always "". Thus, since the digit separator is combined with the first character, it always outputs only the first character.

Answer 5

My solution also allows you to set a threshold for the minimum size of a substring

This is my code:

 def split_string (s, min_str_length = 2, root_string=[], results=[] ): """ :param s: word to split, string :param min_str_length: the minimum character for a sub string :param root_string: leave empty :param results: leave empty :return: nested list of all possible combinations of word split according to the minimum substring length """ for i in range(min_str_length,len(s)): if i == min_str_length: primary_root_string=root_string else: root_string = primary_root_string if len(s[i:])>= min_str_length : results.append(list(chain(*[root_string,[s[:i]],[s[i:]]]))) root_string = list(chain(*[root_string,[s[:i]]])) split_string(s[i:], min_str_length, root_string, results) return results 

Examples of using:

 Input: split_string ('monkey', min_str_length = 1, root_string=[], results=[] ) Output: [['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']] 

or

 Input: split_string ('monkey', min_str_length = 2, root_string=[], results=[] ) Output: [['mo', 'nkey'], ['mo', 'nk', 'ey'], ['mon', 'key'], ['monk', 'ey']] 

Answer 6

Consider more_itertools.partitions :

Given

 import more_itertools as mit s = "monkey" 

demonstration

As it 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 attaching some line:

 [list(map("".join, x)) for x in mit.partitions(s)] 

Exit

 [['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 .