Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
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 Jun 15 '12 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 Jun 15 '12 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 Jun 15 '12 at 10:10
@paulsmith: If you could, you'd have solved P = NP and you'd be a Nobel Prize-winning CS doctor. – DeadMG Jun 15 '12 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 Jun 15 '12 at 14:33

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
Yes you're right! I seem to have missed that use case. So how would you make the algorithm? – paul smith Jun 15 '12 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 ;) – Gerenuk Jun 15 '12 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 (2**n)-1, inclusive. 0 represents the empty set, and (2**n)-1 represents the full set. – John R. Strohm Jun 15 '12 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. – Gerenuk Jun 15 '12 at 10:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.