vamaddur's blog

Can I Find the Nth Lexicographic Subset in Less Than O(N^2) Time?
By vamaddur, history, 7 years ago, In English

Given a set {a, b, c, d}, its non-empty subsets in lexicographic order are as follows: {a, ab, abc, abcd, abd, ac, acd, ad, b, bc, bcd, bd, c, cd, d}

I found an O((sizeofset)^2) method of finding the Nth lexicographically smallest subset here, but I was wondering if there was a faster way to do this.

I know that finding the Nth lexicographically smallest string can be reduced from O((sizeofset)^2) time to O(sizeofset). time, which motivated me to ask this question about a similar reduction for subsets.

Please help, and thanks in advance!

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Hi, it seems like the time complexity is different from the website that you linked. I think it's O((sizeofset)2), not O(N2). And also, is it a set, or a multiset? And what is the constraints of N?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Oh sorry about that! It is O((sizeofset)^2). We are dealing with a set, and the size of the set is at most 100. We also assume that the set is already sorted.

    → Reply
»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

YES YOU CAN

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Assume f[i] — count of subsets we can build with i as the first element. It is easy to proof that f[i] = f[i + 1] * 2. Now you can go down the tree of subsets to build answer. Solution O(n)

→ Reply