11

I want to find all possible partitions of a str without empty strs and must contain ever char (should not contain the original str)

For example:

s = '1234'

partitions(s)  # -> [['1', '2', '3', '4'], ['1', '2', '34'], ['1', '23', '4']
               #     ['12', '3', '4'], ['12', '34'], ['1', '234'], ['123', '4']]
               # should not contain ['1234']

EDIT: Can be in any order

Why My Question Is Not a Duplicate:

I don't want permutations that is:

from itertools import permutations

s = '1234'
permutations(s) # returns ['1', '2', '3', '4'], ['1', '2', '4', '3']...

But I want the the string partitioned into many lengths (Please Have a Look at the First Code)

Thanks!

Sriv
  • 386
  • 1
  • 3
  • 16

3 Answers3

15

You can define a recursive (generator) function. The idea is: to combine prefixes of the string of all length with all the partitions of the remaining string.

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

Results for partitions("1234"):

['1', '2', '3', '4']
['1', '2', '34']
['1', '23', '4']
['1', '234']
['12', '3', '4']
['12', '34']
['123', '4']
['1234']

Note that this does contain ['1234'] but this can easily be filtered afterwards, e.g. as print([p for p in partitions("1234") if len(p) > 1]), or you could collect the results in a list and then pop the last element. Adding this directly to the recursive function would be more complicated, as each but the top-level call should return that "full" partition.

tobias_k
  • 81,265
  • 12
  • 120
  • 179
  • It works, thanks, but do you have any idea how to remove the original str? – Sriv Sep 04 '18 at 14:09
  • 1
    @Srivaths See the last paragraph. It seems to be much simpler to remove it afterwards instead of adapting the algorithm. – tobias_k Sep 04 '18 at 14:13
  • 2
    the sublist with `len(sublist) == 1` will always be generated last, so you do not have to traverse through the whole thing with a new list-comprehension to filter it out. You can just do `res = list(partitions); res.pop()`. +1 – Ma0 Sep 04 '18 at 14:17
  • @Ev.Kounis Just wanted to add this, but then again, this only works when collecting in a list, which has drawbacks of its own. – tobias_k Sep 04 '18 at 14:23
  • if i am not mistaken, the length of the list is given by 2**(len(string)-1)-1 so casting the result to a list should not be so bad for *resonable-sized* input, but sure. – Ma0 Sep 04 '18 at 14:27
4

An idea could be as follows. Given a string "1234", you partition the string computing the positions of the substrings.

import itertools

s="1234"

possibilities = []

for i in range(1,len(s)):

    comb = itertools.combinations(range(1,len(s)), i)

    possibilities+= [[s[0:c[0]]] + [s[c[i]:c[i+1]] for i in range(len(c)-1)] + [s[c[-1]:]] for c in comb]

output

#[['1', '234'], ['12', '34'], ['123', '4'], ['1', '2', '34'], ['1', '23', '4'], ['12', '3', '4'], ['1', '2', '3', '4']]

This solution does not contain ['1234'] in the output (it's because the main loop starts from 1 and not from 0).

Just a footnote.
The number of ways to partition a string without including the original string is

enter image description here

The idea on which this solution is based is this. On generating each of them according to the formula above. The number is large, and no polynomial time algorithm can exist (at least you have to generate each element of the output, so Ω(2^n) is a lower bound for the general problem).

abc
  • 11,579
  • 2
  • 26
  • 51
0

Use code from this SO question to list all substrings (ported to python 3), then remove the main string. Then create all permutations and filter only the allowed ones.

import itertools


def get_all_substrings(input_string):
    length = len(input_string)
    return [input_string[i:j+1] for i in range(length) for j in range(i,length)]


def filter_func(string, iterable):
    """ Leave only permutations that contain all letters from the string and have the same char count. """
    all_chars = ''.join(iterable)
    return True if len(all_chars) == len(string) and all(char in all_chars for char in string) else False


s = '1234'
partitions = get_all_substrings(s)
partitions.remove(s)  # remove '1234' (results should be only substrings not equal to the original string)

results = []
# create all permutations of all substrings, for all sub-lengths of the string length (1, 2, 3...)
for i in range(len(s)):
    permutations = list(itertools.permutations(partitions, i + 1))
    accepted_permutations = tuple(filter(lambda p: filter_func(s, p), permutations))  # filter out unwanted permutations
    results += accepted_permutations

res = list(set(tuple(sorted(l)) for l in results))  # filter out duplicates with different order
print(res)

This is not as nice as the recursive solution above, but I already crated it, so posting it :D Edit: Reworked the question completely.

Filip Happy
  • 575
  • 5
  • 17