All Permutations (All Permutations)

Description

Generate all permuttaions of the characters/elements in a string/array.

Parameters

$n$: number of elements

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Steinhaus–Johnson–Trotter algorithm	1963	$O(n)$ on specific permutations	$O({1})$	Exact	Deterministic	Time
Tompkins–Paige algorithm	1956	$O(n)$ on specific permutations	$O(n)$	Exact	Deterministic	Time
Heap's algorithm	1963	$O(n)$ per permutation	$O(n)$	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff