Finding All Subsequences of a String Using Python | Iterative vs Recursive

Subsequences are an interesting and widely used concept in computer science, especially in areas involving string manipulation and analysis such as algorithms, data mining, and bioinformatics. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Understanding Subsequences

For any given string, a subsequence is any sequence such that it can be derived from the given string by deleting some or no characters keeping the order of the remaining characters in the given string to be the same.

"""


For the string "abc", the subsequences are

'abc', 'ab', 'ac', 'a', 'bc', 'b', 'c', ''


"""

The total number of subsequences of a string of length n is 2n, including the empty string, which is considered a subsequence by definition.

Note: Total number of subsequences of a string of length n is 2n.
This is because in a subsequence of a string of n characters, there are ‘2’ possibilities for each character (ch) ie,

1) ‘ch’ is included in the subsequence
2) ‘ch’ is not included in the subsequence

Using combinatorics, number of possible sequences will be:

2 x 2 x....2 (n times)

2n

Why Find Subsequences?

String subsequences find usability in various problems across numerous fields. Consider these applications:

Pattern Matching: In computational biology, subsequences can be used to find patterns in DNA or protein sequences. Finding common subsequences among the genes of different organisms helps in understanding functional similarities. For instance, the longest common subsequence (LCS) can help identify similar functional regions across species.

Data Analysis: In data mining, subsequences can help in sequence mining, discovering frequent patterns. In academic and literary contexts, finding common subsequences between different documents can help identify instances of plagiarism. The LCS can highlight copied sections even if parts of the text have been modified.

Cryptography: Subsequences can also be applied in cryptography for analyzing sequences of keys or data streams to ensure security protocols are not susceptible to certain types of attacks. In deciphering encrypted messages, analyzing the subsequences of characters can help in understanding the frequency and distribution of characters, aiding in breaking classical ciphers.

Finding Subsequences – Recursive Approach

The approach to finding all subsequences of a string involves using recursion. A recursive function can be designed to decide, for each character, whether to include it in the current subsequence or not.

Code Implementation

def find_subsequences(s):
    """Find all subsequences of a given string s."""
    subsequences = []

    def recurse(current, index):
        if index == len(s):             # reached the end of the string length
            subsequences.append(current)
            return
        # Include the current character
        recurse(current + s[index], index + 1)
        # Do not include the current character
        recurse(current, index + 1)

    recurse("", 0)
    return subsequences


# Example Usage
string = "abc"
all_subsequences = find_subsequences(string)
print(all_subsequences)

Output

['abc', 'ab', 'ac', 'a', 'bc', 'b', 'c', '']

Note: The above code syntax, where a function is defined within another function, is known as a nested function, or more formally, an inner function in Python. Nested functions encapsulate their behavior within the outer function. They avoid cluttering the global namespace and keeps the functions locally scoped to where they are used.

Time complexity: O(2ⁿ), n is the length of the string. This is because the total number of subsequences generated is 2n.
Auxiliary Space: O(n*2ⁿ), n for the maximum depth of the recursion stack and 2n for the number of generated subsequences.

Some useful points:

• find_subsequences(s): The main function that initializes the list to hold all subsequences.
• recurse(current, index): A helper function defined within the main function. It takes the current subsequence being built (current) and the current index in the string (index).
• when index equals the length of the string, the current subsequence is added to the list of subsequences.
• as the number of subsequences grows exponentially with the length of the string, be cautious with long strings, as this can quickly consume a large amount of memory.

Finding Subsequences – Iterative Approach

While recursive method is intuitive, it can be less efficient for large strings due to higher memory usage and potential stack overflow issues. An alternative way is to use an iterative method, particularly leveraging bit manipulation, which may offer more efficient and scalable solutions.

The bit masking method involves using binary numbers as masks to decide whether to include each element of the original string in the current subsequence. This method is based on the fact that for a string of length n, there are 2ⁿ possible subsequences, including the empty one. Each subsequence can be represented by a binary number where each bit determines the presence of an element – ith character: is present if ith bit is 1 and is not present if ith bit is 0.

Bitmasking is discussed in detail in this post – Bitmasking

Code Implementation

def find_subsequences(s):
    """Generate all subsequences of a given string using bit manipulation."""
    subsequences = []
    total = 1 << len(s)  # 2^n subsequences

    for i in range(total):  # from 0 to 2^n - 1
        subseq = []
        for j in range(len(s)):  # check each bit position
            if i & (1 << j):  # if j-th bit of i is set, include s[j] in the subsequence
                subseq.append(s[j])
        subsequences.append(''.join(subseq))  # join all characters to form the subsequence

    return subsequences


# Example usage
string = "abc"
all_subsequences = find_subsequences(string)
print(all_subsequences)

Output

['', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']

Time complexity: O(2ⁿ), n is the length of the string. This is because the outer loop runs 2n times, where n is the length of the string. Each iteration corresponds to one of the 2n subsequences.
Auxiliary Space: O(n*2ⁿ), n for the length of the each subsequence (upper bound) and 2n for the number of generated subsequences.

Some useful points:

• total = 1 << len(s): This calculates 2n, which is the total number of subsequences.
• if i & (1 << j): This checks if the jth bit in i is set. If it is, it means the jth character of the string should be included in the current subsequence.
• in practical scenarios iterative method is more space-efficient than recursive methods, especially for large strings, as it avoids the overhead of the call stack.
• Python has a default recursion limit set by sys.getrecursionlimit(), which is typically around 1000. This can be problematic for generating all subsequences of larger strings recursively.

Both approaches have an exponential growth in time and space complexities as the length of the input string increases. While both have a time complexity of O(n * 2n) when considering the work done per each generated subsequence, the iterative method’s space complexity also effectively scales in a similar way due to the direct storage of each subsequence. The recursive method may have additional overhead due to recursive calls and call stack usage, when comparing with the iterative approach.

To conclude, identifying all subsequences of a string finds its utility in numerous applications across various fields within computer science. The provided Python scripts use recursion and bitmasking to effectively manage the combinatorial aspects of the problem.