0

Possible Duplicate:
How to find all possible subsets of a given array?

How can all ways of selection of items be generated efficiently using C++?

For example, if there are there items A, B and C.

[A,B,C] => [A], [B], [C], [A,B], [B,C], [A,C], [A, B, C]
Community
  • 1
  • 1
Nemo
  • 4,601
  • 11
  • 43
  • 46

3 Answers3

2

Essentially, you can break the problem down into: "For each item, will it be part of the set or not". If you can find all combinations of that then you can find all possible ways of selecting items.

A way of representing whether an item is in the set or not is with a Boolean. True or 1 if it is in the set and false or 0 if it isn't. So we need a Boolean for each of the items. This brings to mind an int or another type as they are all essentially, a bunch of bits.

Now how can we find all combinations of those booleans. There is a simple answer: loop through all the integers. For example:

ABCD Number in base 10
0000 0
0001 1
0010 2
0011 3
0100 4
.... ...
1111 (2^4) - 1

We know there are 2^4 answer since each item can be in the set or not in the set so there are 2 possibilities for each item. If there are 4 element then there are 2*2*2*2 or 2^4 combinations.

There's also an easy way to find 2^n. Simply doing 1 << n.

This leads us to the simple answer:

for (int i = 0; i < (1 << n); i++) {
    // Here the ath bit of i will be set if the ath item is part of the set
}

Note that this will include the empty set, ie [ ]. If you don't want this, simply start the loop from 1 instead of 0.

Hope this helps.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
flight
  • 7,162
  • 4
  • 24
  • 31
  • That's exactly what I said, why you add such similar answer? – Saeed Amiri Sep 24 '11 at 08:55
  • 2
    @SaeedAmiri Look it's a long answer. Just because you submitted first doesn't mean your answer is correct. I've added more to my answer than just your answer and even if it was the same it actually takes *time* to write an answer. Perhaps when you submitted my answer, I was still writing mine. – flight Sep 24 '11 at 08:58
  • I agree you can't write this in 2 mins, I'll remove downvote. – Saeed Amiri Sep 24 '11 at 09:01
2

For that input set:

#include <iostream>

void print(int b, char *a, int n)
{
   for(int i = 0 ; i < n ; i++)
   {
     if( b & 0x1)  std::cout << a[i];
     b = b >> 1;
   }
   std::cout << std::endl; 
}

int main() {
        char a[] = {'A','B','C'};
        for(int i = 1 ; i < 8 ; i++ )
            print(i,a,3);
        return 0;
}

Output:

A
B
AB
C
AC
BC
ABC

Demo : http://ideone.com/2Wxbi

Now it's your turn to improve and generalize this approach, and find it's limitations.

Nawaz
  • 353,942
  • 115
  • 666
  • 851
  • That's exactly what I said, why you add such similar answer? – Saeed Amiri Sep 24 '11 at 08:55
  • 2
    @SaeedAmiri: You think I *plagiarise* your ideas? – Nawaz Sep 24 '11 at 08:56
  • 2
    @SaeedAmiri: and therefore downvoted it? – Nawaz Sep 24 '11 at 08:57
  • No, but when I wrote it 4 minutes before you sure you can see it, and there isn't to need same post. I downvote you because you wasn't care about prev answers. – Saeed Amiri Sep 24 '11 at 08:59
  • 2
    @SaeedAmiri: After your post, I didnot *start* writing my post, rather I started it when I saw there was no answer posted. It's just that I was writing it on ideone.com, and then copy-pasted it here, and formatted it; all these took time. Also, until you *refresh* the page, it doesn't show up the new answers. By the way, after posting, why I didn't delete it (even after seeing your post), because you only described the steps, it doesn't have code-demo. Plus, there is no rule that I should delete this answer, simply because the algo matches with yours. – Nawaz Sep 24 '11 at 09:04
  • your current answer is just doing everything for home work, OP doesn't said that it's homework but `writing .... in c++` what does it mean? Also Michał Šrajer, hint was enough to do this in c++(I mean he had a great hint on how to write code). I mean your answer is not useful in all nor for OP nor for others, also I think after you post it you see 3 different answer and again you don't care a ... about them. – Saeed Amiri Sep 24 '11 at 09:11
  • @SaeedAmiri: Since Michael's *hint was enough to do this in c++*) (I mean, *you mean he had a **great hint** on how to write code*), so please delete your answer, **because** you seem to care for Michael's answer soooooooooo much. ;-) – Nawaz Sep 24 '11 at 09:17
  • Nawaz, Read my answer carefully, I wrote that I'm not going to write code (because it's not technical problem to help with code), I mean that if there was a need to code just hint was enough, If you don't like understand it I can't do anymore and again I think you should remove your answer because it's totally useless. – Saeed Amiri Sep 24 '11 at 09:21
  • @Nawaz Is there any limitation? When generalized, it works well in all cases. – Nemo Sep 24 '11 at 09:21
  • Now it's good to customize your code for ajan to complete the homework. – Saeed Amiri Sep 24 '11 at 09:23
  • FYI it is not homework. It was an interview question and hence the tag. – Nemo Sep 24 '11 at 09:25
  • @SaeedAmiri: That is your opinion. And I don't agree with it, and so I will not delete this post. – Nawaz Sep 24 '11 at 09:36
  • @Ajan: Every solution in this world has limitations; it's just that you discover them when they fail. Try applying this algorithm for `N` characters, where `N > sizeof(int) * CHAR_BIT`. If `CHAR_BIT` is `8`, and `sizeof(int)` is `4`, then try with minimum `33` characters. – Nawaz Sep 24 '11 at 09:38
1

If you have N elements (here N=3), then iterate i from 1 to (1<<3) and in each iteration look at binary value of i.

Michał Šrajer
  • 30,364
  • 7
  • 62
  • 85