An algorithm for generating subsets of fixed size with a strong minimal change property (Q1060849): Difference between revisions

We present an algorithm for generating a list \(S_ 1,S_ 2,...,S_ m\) \((m=\left( \begin{matrix} n\\ k\end{matrix} \right))\) of all subsets of size k of a set of size n. The algorithm has two important properties: it is a minimal change algorithm in that successive subsets \(S_ i\) and \(S_{i+1}\) are minimally different, and it is fast in the sense that the time required to produce the list is bounded by a constant multiple of \(\left( \begin{matrix} n\\ k\end{matrix} \right)\).