combinatorics.md

Combinatorial algorithms

Table of contents

• Permutations
  • Algorithm L
  • Heap’s algorithm
  • Random permutations

---

Permutations

Algorithm L

Algorithm L for the given sequence of n initially sorted elements {a0 ≤ a1 ≤ ... ≤ an-1}, generates all permutations visiting them in the lexicographic order. Gist of the algorithm: for the current permutation, find the longest decreasing subsequence on the right, {...ap ≤ ai > aj > ... > ak}, find the next front element af > ap with the largest possible f in the range [i, k], swap af and ap, and then put the remaining elements in the ascending order, i.e. reverse the subsequence {ai...ap...ak}.

📝

• This algorithm is used in some implementations of std::next_permutation in the standard library.

🔗

• std::next_permutation implementation explanation – Stack Overflow

📖

• Sec. 7.2.1.2: Generating all permutations – D.E.Knuth. The art of computer programming. Vol. 4A: Combinatorial algorithms, Part 1 (2011)

Heap’s algorithm

Heap’s algorithm generates all possible permutations of n objects. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other n - 2 elements are not disturbed.

🔗

• Heap’s algorithm – Wikipedia
• Heap algorithm for permutations – Stack Overflow

Random permutations

See Shuffling – Randomized algorithms.