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})$ auxiliary	Exact	Deterministic	Time
Tompkins–Paige algorithm	1956	$O(n)$ on specific permutations	$O(n)$ auxiliary	Exact	Deterministic	Time
Heap's algorithm	1963	$O(n)$ per permutation	$O(n)$ auxiliary	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Space-Time Tradeoff Improvements