2

This is the algorithm (pseudocode) I have right now for finding all subsets for a given set with length k:

void allSubsets(set[]) { for (i = 0; i<k; i++) { for (j = i + 1; j<k; j++) { print(set[i...j]); } } }


But it's run-time is O(n^2). Can anybody improve this?

Improve this question
5
  • 4
    O(n^2) is better than possible, because there are \binom{n}{k} subsets of size k. For fixed k, you're looking at O(n^k) being optimal.
    – Peter Taylor
    CommentedJun 15, 2012 at 9:35
  • The number of subsets is 2^n, so it's impossible for algorithm to be better than O(2^n) - because it has to create the output at least.
    – user281377
    CommentedJun 15, 2012 at 10:02
  • I see, so what you're saying is we can't do any clever tricks to avoid O(2^n). Right?
    – paul smith
    CommentedJun 15, 2012 at 10:10
  • @paulsmith: If you could, you'd have solved P = NP and you'd be a Nobel Prize-winning CS doctor.
    – DeadMG
    CommentedJun 15, 2012 at 10:24
  • Better than O(2^n) is possible for fixed k. I don't think anyone will give a better answer than the accepted one for stackoverflow.com/questions/127704/… , but I can't flag this question as a duplicate of a question on StackOverflow.
    – Peter Taylor
    CommentedJun 15, 2012 at 14:33

1 Answer 1

Reset to default
2

From what I understand this doesn't work. You wouldn't find "AC" in the set "ABCD" (i.e. holes). To find all subsets think that each element is either inside the subset or not. Which is basically a binary yes, no. Therefore you can cycle over all numbers with k 0/1 bits to find all combinations.

Improve this answer
4
  • Yes you're right! I seem to have missed that use case. So how would you make the algorithm?
    – paul smith
    CommentedJun 15, 2012 at 10:05
  • 1
    I'd use an integer counter. In each iteration you iterate over all bits by checking if the number is odd/even and then you shift bits to the right (like divide by 2) and check again. This way you iterate over all bits of the counter and decide whether to include a particular element or not. The rest is up to you to find out ;)
    – Gere
    CommentedJun 15, 2012 at 10:28
  • 1
    @Gerenuk, you're over-complicating it. Consider a set S with n elements. Any subset of S may be represented exactly by an n-bit bitmap. To generate all possible subsets, generate all possible n-bit bitmaps, i.e., count from 0 to (2n)-1, inclusive. 0 represents the empty set, and (2n)-1 represents the full set.
    – John R. Strohm
    CommentedJun 15, 2012 at 10:34
  • 2
    @john: You a) didn't understand my algorithm written in non-technical terms which is exactly what you propose; and b) you still haven't solved the practical question of returning sets and not some encoded representation. Tech-talk alone is fruit-less.
    – Gere
    CommentedJun 15, 2012 at 10:40

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.