FilesExpand file tree

master

/

all_permutations.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

51 lines (39 loc) · 1.46 KB

master

/

all_permutations.py

Copy path

Top

File metadata and controls

• Code
• Blame

51 lines (39 loc) · 1.46 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

"""

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)