patternMinor
Efficiently enumerate all subsets of an ordered set
Viewed 0 times
efficientlyallsetsubsetsorderedenumerate
Problem
What's the most efficient way to enumerate all (ordered) subsets of an ordered set? So, for example, given the ordered set $\{2, 5, 6\}$ (using the normal ordering for integers), I need the following:
$$\{\}, \{2\}, \{5\}, \{6\}, \{2, 5\}, \{2, 6\}, \{5, 6\}, \{2, 5, 6\}.$$
Smaller subsets should come first, but the ordering of the subsets of equal size is not important.
I'm looking for an algorithm that is efficient both in theory and in implementation (in a general purpose programming language) for very large sets.
$$\{\}, \{2\}, \{5\}, \{6\}, \{2, 5\}, \{2, 6\}, \{5, 6\}, \{2, 5, 6\}.$$
Smaller subsets should come first, but the ordering of the subsets of equal size is not important.
I'm looking for an algorithm that is efficient both in theory and in implementation (in a general purpose programming language) for very large sets.
Solution
One possibility is to generate separately all subsets of size $k$ using the following recursive approach:
A $k$-subset of $a_1,\ldots,a_n$ is either a $k$-subset of $a_2,\ldots,a_n$ or $a_1$ adjoined to a $(k-1)$-subset of $a_2,\ldots,a_n$.
Run this recursive algorithm for $k=0,\ldots,n$. If you're careful, you will get a lexicographically ordered output.
A $k$-subset of $a_1,\ldots,a_n$ is either a $k$-subset of $a_2,\ldots,a_n$ or $a_1$ adjoined to a $(k-1)$-subset of $a_2,\ldots,a_n$.
Run this recursive algorithm for $k=0,\ldots,n$. If you're careful, you will get a lexicographically ordered output.
Context
StackExchange Computer Science Q#33718, answer score: 6
Revisions (0)
No revisions yet.