Python-2/backtracking/all_permutations.py at master · https-github-com-nzysoft/Python-2 · GitHub

History

51 lines (39 loc) · 1.46 KB

Raw

"""

In this problem, we want to determine all possible permutations

of the given sequence. We use backtracking to solve this problem.

Time complexity: O(n! * n),

where n denotes the length of the given sequence.

"""

from __future__ import annotations

def generate_all_permutations(sequence: list[int | str]) -> None:

create_state_space_tree(sequence, [], 0, [0 for i in range(len(sequence))])

def create_state_space_tree(

sequence: list[int | str],

current_sequence: list[int | str],

index: int,

index_used: list[int],

) -> None:

"""

Creates a state space tree to iterate through each branch using DFS.

We know that each state has exactly len(sequence) - index children.

It terminates when it reaches the end of the given sequence.

"""

if index == len(sequence):

print(current_sequence)

return

for i in range(len(sequence)):

if not index_used[i]:

current_sequence.append(sequence[i])

index_used[i] = True

create_state_space_tree(sequence, current_sequence, index + 1, index_used)

current_sequence.pop()

index_used[i] = False

"""

remove the comment to take an input from the user

print("Enter the elements")

sequence = list(map(int, input().split()))

"""

sequence: list[int | str] = [3, 1, 2, 4]

generate_all_permutations(sequence)

sequence_2: list[int | str] = ["A", "B", "C"]

generate_all_permutations(sequence_2)

Python-2/backtracking/all_permutations.py at master · https-github-com-nzysoft/Python-2 · GitHub

Uh oh!

Expand file tree

Breadcrumbs

all_permutations.py

Latest commit

History

Breadcrumbs

all_permutations.py

File metadata and controls