Generare submultimi complexitate 2^n: bitwise-subsets.cpp

bitwise-subsets.cpp

#include <iostream>


//2 for-uri...O(n^2)
//n * 2^n 

/*
A = {1,2,3} numarul de submultimi = 8 pentru ca avem 2^3 subsets
1. backtracking
2. iterativ
3. Bitwise

1 =  001 {1}
2 =  010 {2}
3 =  011 {1,2}
4 =  100 {3}
5 =  101 {1,3}
6 =  110 {2,3}
7 =  111 {1,2,3}
8 =  000 {}
Complexitate O(2^n) = 

n = 3
1 = 0000 0000
         1000 = 1*2^3 + 0 * 0*2^2 + 0 * 2^1 + 0 * 2^1 =  8

         Complexitate Time: n 2^n 

         for(int i = 1; i <= n; ++i) {

	            for(int j = 1; j <= m; ++j) {
	                ...
	            }
         }
         O(n^2)
*/

void gen(int n) {

	 for(int mask = 1; mask <= (1<<n); ++mask) {//avem 2^n = submultimi, 0

          std::cout<<"{";

          for(int i = 0; i < n; ++i) {

          	       if(mask & (1<<i)) {

          	       	  std::cout<<i+1<<" ";
          	       }
          }

          std::cout<<"}";

          std::cout<<std::endl;
	 };
}


/*
5 =  101 {1,3}

i = 0
i = 1
i = 2

mask = 1,2,3,4,5,6,7,8
5 scris in baza 2 = 101

101 & 
010
---



1 = 0000 0000 0000 0000 0000 0000 0000 0001

*/

int main(int argc, char const *argv[])
{
	
	int n ;
	n = 5;

	gen(n); 

	std::cout<<sizeof(int);
	return 0;
}