Cross The Streams About

All Partitions of a String

Let’s say we have a string "abcd". Our objective: we want to generate every possible way the string can be partitioned, or split into substrings (e.g. ["a", "b", "c", "d"] vs ["ab", "cd"]). The returned data could have different formats for this problem, but let’s say we want to return an array of arrays containing the partitioned sub-strings.

Let’s first think through every way we can split up "abcd". Then let’s take a look at a couple solutions to this problem, implemented in Ruby.

Thinking it through

A good place to start is to consider how many times I’m splitting the string. Our base case is the entire string of "abcd", where we don’t partition the string at all:

# base case, not much happening yet 
["abcd"]

If I’m splitting the string once, I can split "a" from "bcd", "ab" from "cd", or "abc" from "d":

# base case, the entire string
└── # 1 partition

["abcd"]
├── ["a", "bcd"]
├── ["ab", "cd"]
└── ["abc", "d"]

Those are all our options for splitting the string once!

What if I split the string twice? That’s necessarily a sub-decision after we’ve already split the string once, so we’re depending on the partitions we placed above.

In the case of our string that was split as ["a", "bcd"], we can add ["a", "b", "cd"] and ["a", "bc", "d"]. In the case of our string that was split as ["ab", "cd"], we can add one more partition after c with ["ab", "c", "d"].

The above process is a tree of placing new partitions in our string, like so:

# base case, the entire string
└── # 1 partition added
    └── # 2 partitions added
        └── # 3 partitions added (this is the deepest level of the tree for "abcd")
["abcd"]
├── ["a", "bcd"]
│   ├── ["a", "b", "cd"]
│   │   └── ["a", "b", "c", "d"]
│   └── ["a", "bc", "d"]
├── ["ab", "cd"]
│   └── ["ab", "c", "d"]
└── ["abc", "d"]

Using Recursion

Since this problem is defined by a tree of decisions (i.e. where to place partitions), it lends itself to recursion:

def recursive_partitions(string:, partitions: [], result: [])
  # We start with the entire string as a base case
  # When we recurse, string will be the right slice
  # from within the for loop below
  # partitions will contain the left slice from within the for loop,
  #   plus prior left slices from higher in the call stack
  new_partition = (partitions + [string])
  result.unshift(new_partition)

  # Iterate every index we'll place a partition at, 1..last index
  slices = []
  for i in (1..string.length - 1)
    left_slice = string[0..i-1] # e.g. a, ab, abc
    right_slice = string[i..-1] # e.g. bcd, cd, d
    slices << [left_slice, right_slice]
  end

  slices.reverse_each do |slice_arr|
    left_slice, right_slice = slice_arr
    # Use the slices we've collected in recursion
    recursive_partitions(
      string: right_slice,
      partitions: (partitions + [left_slice]),
      result: result,
    )
  end

  # All done!
  result
end

The above will return the possible partitions of "abcd":

> recursive_partitions(string: "abcd")
[
      ["a", "b", "c", "d"],
      ["a", "b", "cd"],
      ["a", "bc", "d"],
      ["a", "bcd"],
      ["ab", "c", "d"],
      ["ab", "cd"],
      ["abc", "d"],
      ["abcd"]
]

Using A Stack

We can instead use a stack-based approach to accomplish the same functionality as the recursion above, which avoids using the overhead of the call stack.

def stack_partitions(string:)
  result = []
  result << [string]
  # We start the stack with a base case of the entire string
  # On each iteration, we'll have an "unpartitioned" part of the string and
  # a complementing array of partitions. We'll then partition that "unpartitioned" part.
  stack = [[[], string]]

  while stack.any?
    partitioned, unpartitioned = stack.pop
    # Add this new possible set of partitions to the results, unless its the original string
    result.unshift((partitioned + [unpartitioned])) unless unpartitioned == string
    for i in (1..unpartitioned.length - 1)
      left_slice = unpartitioned[0..i-1]
      right_slice = unpartitioned[i..-1]
      stack << [(partitioned + [left_slice]), right_slice]
    end
  end

  result
end
> stack_partitions(string: "abcd")
[
      ["a", "b", "c", "d"],
      ["a", "b", "cd"],
      ["a", "bc", "d"],
      ["a", "bcd"],
      ["ab", "c", "d"],
      ["ab", "cd"],
      ["abc", "d"],
      ["abcd"]
]

Time and Memory Complexity

Both the time and memory complexity of our algorithm are dictated by the points in the string we can place partitions. With each of these, as in the tree diagram above, we have to navigate a tree of further choices about placing partitions, which leads to exponential time and memory complexities.

Any string will have N-1 locations where we can split the string. In the case of "abcd", there are three such locations. We end up with 2^3 possible partitions in our 2-D array after placing partitions 2^3 times. This gives us time and memory complexities of O(2^N-1), or simply O(2^N).

References

For futher reference on this problem, here are some good resources: