liveBook · Manning

Recursive combination enumeration

As explained in Fabulous Adventures in Data Structures and Algorithms

Recursive combination generation enumerates combinations by recursively separating those that exclude a final element from those that include it.

Recursive combination enumeration generates combinations without mutation by splitting them into those that exclude the final element and those that include it. Since the final element can only appear at the right end, this preserves lexicographic order naturally. section 6.3.1

Ordered output

Generating four-element combinations from six elements produces 0123, 0124, 0134, 0234, 1234, and continues through 2345.

How Fabulous Adventures in Data Structures and Algorithms covers it

How deep it goes
Explains recursive cases, immutable construction, complexity, and stack usage, but stops short of generating the p-th combination.
Examples
Uses C# Combinations2 code and the ordered four-from-six output sequence.
What it assumes
Assumes familiarity with combinations, recursion, C# iterators, and the immutable deque used to store results.
What you can do after
Build it from scratch using recursive C# iterators and an immutable deque, with O(n) worst-case time per combination and stack space.
How it connects
Connects recursion with lexicographic ordering, immutable deques, and amortized operation costs.
Cover of Fabulous Adventures in Data Structures and Algorithms
liveBookmanning.com
Read Fabulous Adventures in Data Structures and Algorithms on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Fabulous Adventures in Data Structures and Algorithms. The section links point to the parts of the book it draws on.