Блог пользователя vamaddur

Автор vamaddur, история, 7 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

YES YOU CAN

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)