backtracking.all_permutations

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.

Attributes

sequence

sequence_2

Functions

create_state_space_tree(→ None)

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

generate_all_permutations(→ None)

Module Contents

backtracking.all_permutations.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.

Parameters:

  • sequence – The input sequence for which permutations are generated.

  • current_sequence – The current permutation being built.

  • index – The current index in the sequence.

  • index_used – list to track which elements are used in permutation.

Example 1: >>> sequence = [1, 2, 3] >>> current_sequence = [] >>> index_used = [False, False, False] >>> create_state_space_tree(sequence, current_sequence, 0, index_used) [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Example 2: >>> sequence = [“A”, “B”, “C”] >>> current_sequence = [] >>> index_used = [False, False, False] >>> create_state_space_tree(sequence, current_sequence, 0, index_used) [‘A’, ‘B’, ‘C’] [‘A’, ‘C’, ‘B’] [‘B’, ‘A’, ‘C’] [‘B’, ‘C’, ‘A’] [‘C’, ‘A’, ‘B’] [‘C’, ‘B’, ‘A’]

Example 3: >>> sequence = [1] >>> current_sequence = [] >>> index_used = [False] >>> create_state_space_tree(sequence, current_sequence, 0, index_used) [1]

backtracking.all_permutations.generate_all_permutations(sequence: list[int | str]) → None
backtracking.all_permutations.sequence: list[int | str] = [3, 1, 2, 4]
backtracking.all_permutations.sequence_2: list[int | str] = ['A', 'B', 'C']