iframe-proxy | Sunbelt Computer Software

93 lines (76 loc) · 2.16 KB

In this problem, we want to determine all possible subsequences
of the given sequence. We use backtracking to solve this problem.
Time complexity: O(2^n),
where n denotes the length of the given sequence.
from __future__ import annotations
from typing import Any
def generate_all_subsequences(sequence: list[Any]) -> None:
    create_state_space_tree(sequence, [], 0)
def create_state_space_tree(
    sequence: list[Any], current_subsequence: list[Any], index: int
    Creates a state space tree to iterate through each branch using DFS.
    We know that each state has exactly two children.
    It terminates when it reaches the end of the given sequence.
    :param sequence: The input sequence for which subsequences are generated.
    :param current_subsequence: The current subsequence being built.
    :param index: The current index in the sequence.
    Example:
    >>> sequence = [3, 2, 1]
    >>> current_subsequence = []
    >>> create_state_space_tree(sequence, current_subsequence, 0)
    [3, 2, 1]
    >>> sequence = ["A", "B"]
    >>> current_subsequence = []
    >>> create_state_space_tree(sequence, current_subsequence, 0)
    ['A', 'B']
    >>> sequence = []
    >>> current_subsequence = []
    >>> create_state_space_tree(sequence, current_subsequence, 0)
    >>> sequence = [1, 2, 3, 4]
    >>> current_subsequence = []
    >>> create_state_space_tree(sequence, current_subsequence, 0)
    [2, 3, 4]
    [1, 3, 4]
    [1, 2, 4]
    [1, 2, 3]
    [1, 2, 3, 4]
    if index == len(sequence):
        print(current_subsequence)
        return
    create_state_space_tree(sequence, current_subsequence, index + 1)
    current_subsequence.append(sequence[index])
    create_state_space_tree(sequence, current_subsequence, index + 1)
    current_subsequence.pop()
if __name__ == "__main__":
    seq: list[Any] = [1, 2, 3]
    generate_all_subsequences(seq)
    seq.clear()
    seq.extend(["A", "B", "C"])
    generate_all_subsequences(seq)

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

Uh oh!

FilesExpand file tree

all_subsequences.py

Latest commit

History

all_subsequences.py

File metadata and controls