Find all the ways to choose $k$ objects from a list of $n$ objects (using a graph?)

Question

I was playing around with graph theory and I noticed that a directed integer graph with unique vertices $V$ and edges $E$ such that each vertex only points to vertices with a higher value can be used to enumerate all $n \choose 2$ ways to choose $2$ values from a total of $\left|V\right|$ possible values.

For example:

Here, $V = \left\{ 0, 1, 2, 3, 4, 5, 6 \right\}$ and $E = \left\{ (0,1),(0,2),\cdots,(5,6) \right\}$ and creating the initial graph is of the order $O(n^2)$. $E$ readily contains all possible pairs of numbers chosen from the list.

I was wondering if the same strategy could be used to enumerate any $n \choose k$ where $0 \leq k \leq n$, or if there are more efficient algorithms for this purpose.

Answer 1

To generalize your approach to $k$-subsets of an $n$-set, you would need to build a hypergraph. Ordinary graph edges are relations between pairs of vertices. Hypergraphs allow relations between arbitrary sets of vertices. They are extremely general objects, essentially representing families of sets.

This question provides two good answers for how to (reasonably) efficiently enumerate these subsets. The first uses bit magic and is a special case when $n$ is small enough. The second takes a recursive approach which saves having to compute the first $k-1$ elements of a $k$ subset multiple times, but only really helps if enumerating over several consecutive values of $k$.