List in lexicographic order all the proper subsets of A B C

List in lexicographic order all the proper subsets of {A, B, C, D}.

Solution

Solution; 11/05/2016.

Given Set { a, B, C, D }

The Problem: Listing Subsets Lexicographically

The initial problem I began working on is as follows: Given a set S of elements drawn from some totally-ordered universe, list all of the subsets of S in lexicographically increasing order. Of course, sets don\'t naturally have a notion of \"lexicographic order,\" but if the sets are of elements that are themselves ordered, we can define a lexicographic ordering on those sets according to the natural definition: we just list all the elements of the sets in increasing order, then compare those strings lexicographically. For example, we have that

{a, b, c} < {a, b, d}

and that

{} < {a, b, c, d}

For simplicity, I\'ll use string notation rather than set notation to encode subsets. For example, I\'ll write abd instead of {a, b, d} and cd instead of {c, d}. I\'ll use the symbol to denote the empty set. In this notation, the subsets of the set abcd are, in lexicographically increasing order:

, a, ab, abc, abcd, abd, ac, acd, ad, b, bc, bcd, bd, c, cd, d

Simply listing all subsets in lexicographically increasing order is tricky, but to make the problem harder let\'s say that we\'re also interested in this follow-up question: given some number k with 0 k < 2ⁿ, what is the kth lexicographically ordered subset of S? For example, given the set abcd and the number 11, we should produce bcd. Ideally, we\'d like an answer that works in time polynomial in log k, since in the worst case k = O(2ⁿ), or even better independently of k.

{    } , { A } , { A, B } { a, c }    { A, D }

{ A, B, C }   { B, C, D }   { A, C, D }

{ B }   { C } { D } .