All ways to partition a string

Problem analysis

Between each pair of adjacent characters, you can decide whether to cut. For a string of size n, there are n-1 positions where you can cut or not, i.e. there are two possibilities. Therefore a string of size n can be partitioned in 2^n-1 ways.

The output consists of 2^n-1 partitions, each having n characters plus separators. So we can describe the output size as f(n) = 2^n-1 * n + s(n) where s(n) ≥ 0 accounts for the partition separators and line separators.

So due to the output size alone, an algorithm solving this problem must have exponential runtime or worse: Ω(2ⁿ).

(0 ≤ c * 2ⁿ = ½ * 2ⁿ = 2^n-1 ≤ 2^n-1 * n ≤ f(n) for all n≥k with positive constants c=½, k=1)

---

Solution

I chose to represent a partition as integer. Each bit in cutpoints determines whether to cut between characters i and i+1. To iterate through all possible partitions, we just need to go trough all integers between 0 and 2^(n-1) - 1.

Example: For a string of length 4, we go through all integers between 0 and 2^3 - 1 or 0 and 7 or in binary: 000 and 111.

# (python 2 or 3)
def all_partitions(string):
    for cutpoints in range(1 << (len(string)-1)):
        result = []
        lastcut = 0
        for i in range(len(string)-1):
            if (1<<i) & cutpoints != 0:
                result.append(string[lastcut:(i+1)])
                lastcut = i+1
        result.append(string[lastcut:])
        yield result

for partition in all_partitions("abcd"):
    print(partition)

Memory usage:

I think my solution uses O(n) memory with Python 3. Only one partition is generated at a time, it's printed and not referenced anymore. This changes of course, if you keep all results, e.g. by storing them in a list.

In Python 2 replace range with xrange, otherwise all possible cutpoints will be stored in a list, therefore needing an exponential amount of memory.

---

JavaScript solution

// ES6 generator
function* all_partitions(string) {
    for (var cutpoints = 0; cutpoints < (1 << (string.length - 1)); cutpoints++) {
        var result = [];
        var lastcut = 0;
        for (var i = 0; i < string.length - 1; i++) {
            if (((1 << i) & cutpoints) !== 0) {
                result.push(string.slice(lastcut, i + 1));
                lastcut = i + 1;
            }
        }
        result.push(string.slice(lastcut));
        yield result;
    }
}

for (var partition of all_partitions("abcd")) {
    console.log(partition);
}

Tested with NodeJS v4.4.3 (disclaimer: I have not used NodeJS before).

GeeksforGeeks has provided a well-explained solution to this problem:

For string abcd there will be 2^(n-1) i.e. 8 partitions.

(a)(b)(c)(d)
(a)(b)(cd)
(a)(bc)(d)
(a)(bcd)
(ab)(c)(d)
(ab)(cd)
(abc)(d)
(abcd)

The crux of the solution lies in the recursion to print all the permutations.
maintain two parameters – index of the next character to be processed and the output string so far. We start from index of next character to be processed, append substring formed by unprocessed string to the output string and recurse on remaining string until we process the whole string.

// Java program to find all combinations of Non-
// overlapping substrings formed from given
// string

class GFG 
{
    // find all combinations of non-overlapping
    // substrings formed by input string str
    static void findCombinations(String str, int index,
                                 String out)
    {
        if (index == str.length())
            System.out.println(out);

        for (int i = index; i < str.length(); i++)

            // append substring formed by str[index,
            // i] to output string
            findCombinations(str, i + 1, out +
                "(" + str.substring(index, i+1) + ")" );
    }

    // driver program
    public static void main (String[] args) 
    {
        // input string
        String str = "abcd";
        findCombinations(str, 0, "");
    }
}

Time Complexity is O(2^n)

Here's the link to the article: http://www.geeksforgeeks.org/print-ways-break-string-bracket-form/