Python all string subsets combinations

Question

I need all combinations of subsets of a string. In addition, a subset of length 1 can only be followed by a subset of length> 1. For example. for line 4824 result should be:

  [ [4, 824], [4, 82, 4], [48, 24], [482, 4], [4824] ] 

So far, I have managed to get all possible subsets with:

  length = len(number) ss = [] for i in xrange(length): for j in xrange(i,length): ss.append(number[i:j + 1]) 

which gives me:

  ['4', '48', '482', '4824', '8', '82', '824', '2', '24', '4'] 

But I do not know how to combine them.

Answer 1

First write a function to generate all sections of the string:

 def partitions(s): if s: for i in range(1, len(s) + 1): for p in partitions(s[i:]): yield [s[:i]] + p else: yield [] 

Iterates over all possible first segments (one character, two characters, etc.) and combines them with all sections for the corresponding remainder of the string.

 >>> list(partitions("4824")) [['4', '8', '2', '4'], ['4', '8', '24'], ['4', '82', '4'], ['4', '824'], ['48', '2', '4'], ['48', '24'], ['482', '4'], ['4824']] 

Now you can simply filter those that match your condition, i.e. those that do not have two consecutive substrings of length one.

 >>> [p for p in partitions("4824") if not any(len(x) == len(y) == 1 for x, y in zip(p, p[1:]))] [['4', '82', '4'], ['4', '824'], ['48', '24'], ['482', '4'], ['4824']] 

Here zip(p, p[1:]) is the usual recipe for iterating over all pairs of consecutive elements.

---

Update. In fact, including your restriction directly in the partition function is also not that difficult. Just track the last segment and set the minimum length accordingly.

 def partitions(s, minLength=1): if len(s) >= minLength: for i in range(minLength, len(s) + 1): for p in partitions(s[i:], 1 if i > 1 else 2): yield [s[:i]] + p elif not s: yield [] 

Demo:

 >>> print list(partitions("4824")) [['4', '82', '4'], ['4', '824'], ['48', '24'], ['482', '4'], ['4824']] 

Answer 2

it would be interesting to see more test cases, the following algorithm does what you say:

 s="4824" def partitions(s): yield [s] if(len(s)>2): for i in range(len(s)-1, 0, -1): for g in partitions(s[i:]): out = [s[:i]] + g if not any([len(out[i]) == len(out[i+1]) and len(out[i])==1 for i in range(len(out)-1)]): yield out list(partitions(s)) 

You are getting:

 [['4824'], ['482', '4'], ['48', '24'], ['4', '824'], ['4', '82', '4']] 

explanation

I is based on the following algorithm:

 s="4824" def partitions_original(s): #yield original string yield [s] if(len(s)>2): for i in range(len(s)-1, 0, -1): #divide string in two parts #iteration 1: a="482", b="4" #iteration 2: a="48", b="24" #iteration 3: a="4", b="824" a = s[:i] b = s[i:] #recursive call of b for g in partitions_original(b): #iteration 1: b="4", g=[['4']] #iteration 2: b="24", g=[['24']] #iteration 3: b="824", g=[['824'], ['82', '4'], ['8', '24']] yield [a] + g list(partitions_original(s)) 

You are getting:

 [['4824'], ['482', '4'], ['48', '24'], ['4', '824'], ['4', '82', '4'], ['4', '8', '24']] 

problem ['4', '8', '24'] ..... then I have to add if to the code because "a subset of length 1 can only follow a subset with length> 1"

[len(out[i]) == len(out[i+1]) and len(out[i])==1 for i in range(len(out)-1)] return for ['4', '8', '24'] → [True, False] .... any Return True if any element iterable is true

Note

You can also use:

if all([len(out[i]) != len(out[i+1]) or len(out[i])!=1 for i in range(len(out)-1)]):

Answer 3

What I'm doing here is to get every possible split position of the string and exclude the last one.

for example, on some line with 5 numbers "12345" for ex. There are 4 possible positions for splitting a line, name it possibility = (0,0,0,0),(1,0,1,0) ... with (0,0,1,0) mean (don't separate 1 and 2345,don't separate 12 and 345,separate 123 and 45,don't separate 1234 and 5) so that you can get all the possibilities while your condition is checked, as we eliminate the case (1,1,1 ,1).

 import itertools from math import factorial from itertools import product def get_comb(string): L = len(string_) combinisation = [] for possibility in product([0,1], repeat=len(string_)-1): s = [] indexes = [i for i in range(len(string_)-1) if list(possibility)[i]!=0] if sum(indexes) != 0: if sum(indexes) != len(string_)-1: for index in indexes: s.append(string_[:index+1]) s.append(string_[indexes[-1:][0]+1:]) combinisation.append(s) else: combinisation.append(string_) return combinisation string_ = '4824' print "%s combinations:"%string_ print get_comb(string_) string_ = '478952' print "%s combinations:"%string_ print get_comb(string_) string_ = '1234' print "%s combinations:"%string_ print get_comb(string_) >> 4824 combinations: [['482', '4'], ['48', '24'], '4824', ['4', '482', '4'], ['4', '48', '24'], '4824 '] 478952 combinations: [['47895', '2'], ['4789', '52'], ['4789', '47895', '2'], ['478', '952'], ['478', '47895', '2'], '478952', ['478', '4789', '47895', '2'], ['47', '8952'], '478952 ', ['47', '4789', '52'], ['47', '4789', '47895', '2'], ['47', '478', '952'], ['4 7', '478', '47895', '2'], ['47', '478', '4789', '52'], ['47', '478', '4789', '47 895', '2'], ['4', '47895', '2'], ['4', '4789', '52'], ['4', '4789', '47895', '2' ], ['4', '478', '952'], ['4', '478', '47895', '2'], '478952', ['4', '478', '4789 ', '47895', '2'], ['4', '47', '8952'], '478952', ['4', '47', '4789', '52'], ['4' , '47', '4789', '47895', '2'], ['4', '47', '478', '952'], ['4', '47', '478', '47 895', '2'], ['4', '47', '478', '4789', '52'], ['4', '47', '478', '4789', '47895' , '2']] 1234 combinations: [['123', '4'], ['12', '34'], '1234', ['1', '123', '4'], ['1', '12', '34'], '1234 '] 

Answer 4

The normal code can be written like this:

 s=raw_input('enter the string:') word=[] for i in range(len(s)): for j in range(i,len(s)): word.append(s[i:j+1]) print word print 'no of possible combinations:',len(word) 

And the conclusion: enter the line: 4824 [4, 48, 482, 4824, 8, 82, there are no possible combinations: 10