Heap's algorithm generates all possible permutations of n objects and was first proposed by B. R. Heap in 1963. It minimizes movement, generating each permutation from the previous one by interchanging a single pair of elements while leaving the other n minus 2 elements undisturbed, and in a 1977 review of permutation generating algorithms Robert Sedgewick concluded it was at that time the most effective algorithm for generating permutations by computer.
Facts
Time Complexity
Time Complexity (category)Factorial Time -- O(n!) 1 Connections
In Field
Source Heap's Algorithm (Wikipedia)
Uses Design Technique
Source Heap's Algorithm (Wikipedia)
Sources
1. Heap's Algorithm (Wikipedia)
Wikipedia infobox: time complexity factorial
factorial
Uses Design Technique: Recursion, Article body
Described recursively as a decrease and conquer method, Heap's algorithm operates at each step on the k {\displaystyle k} initial elements of the collection.
In Field: Algorithms and Complexity Theory, Lead section
Heap's algorithm generates all possible permutations of n objects.
In Group: Shuffling and Permutation Generation Algorithms, Lead section
generates all possible permutations of n objects
View the SourceWikidata: Heap's Algorithm
Wikidata Q16907296, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.