Given an ordered set [1,2,3,...]
of elements, how do I enumerate the powerset of this set in a depth-first way? That is, I want to see all of the subsets containing 1
before I see any subsets without 1
, then all of the remaining subsets containing 2
(but not 1
) before subsets without 2
(or 1
), etc.
That is, for the set [1,2,3,4]
, I want to generate the following tuples in order:
()
(1,)
(1, 2)
(1, 2, 3)
(1, 2, 3, 4)
(1, 2, 4)
(1, 3)
(1, 3, 4)
(1, 4)
(2,)
(2, 3)
(2, 3, 4)
(2, 4)
(3,)
(3, 4)
(4,)
Ideally, I'd be able to do this in a recursive way, without needing to keep track of which subsets I've already visited.