Get all possible str partitions of any length

Question

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!

Answer 1

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.

Answer 2

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

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

Answer 3

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.