 wasp256 -4 years ago 140
Python Question

# python all combinations of subsets of a string

I need all combinations of subsets of a string. In addition, a subset of length 1 can only be followed by a subset with length > 1. E.g. for string

`4824`
the result should be:

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

So far I managed to retrieve 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 don't know how to combine those now. tobias_k
Answer Source

First, write a function for generating all the partitions 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 []
``````

This iterates all the possible first segments (one character, two characters, etc.) and combines those with all the partitions for the respective 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 just filter those that match your condition, i.e. those that have no 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 a common recipe for iterating over all pairs of consecutive items.

Update: Actually, incorporating your constraint directly into the `partition` function is not that hard, either. Just keep track of 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']]
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download
Latest added