fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void display(int* tab, int k)
  5. {
  6. 	for(int i = 0; i < k; ++i)
  7. 	{
  8. 		cout << tab[i] << ",";
  9. 	}
  10. 	cout << endl;
  11. }
  12.  
  13. unsigned int GetBitPositionByNr(int n, int k)
  14. {
  15. 	if (k <= 0 || n <= 0) return 0;
  16.  
  17. 	unsigned int f = 0, i = 0;
  18. 	while ((1 << i) <= n)
  19. 	{
  20. 		if (n & (1 << i))
  21. 			f++;
  22.  
  23. 		i++;
  24.  
  25. 		if (f==k) return i;
  26. 	}
  27.  
  28. 	return -1;
  29. }
  30.  
  31. unsigned int Combination_n_of_k(int n, int k)
  32. {
  33. 	if (k > n) return 0;
  34. 	if (k == 0 || k == n) return 1;
  35.  
  36. 	if (k * 2 > n) k = n - k;
  37.  
  38. 	unsigned int r = 1;
  39. 	for (int d = 1; d <= k; ++d) 
  40. 	{
  41. 		r *= n--;
  42. 		r /= d;
  43. 	}
  44. 	return r;
  45. } 
  46.  
  47. int main() {
  48. 	// your code goes here
  49.  
  50. 	int n = 4;
  51. 	int k = 2;
  52.  
  53.     int combination  = (1 << k) - 1;
  54.     int new_combination = 0;
  55.     int change = 0;
  56.  
  57. 	while (false)
  58.     {
  59.         // return next combination
  60.         cout << combination << endl;
  61.  
  62.         // find first index to update
  63.         int indexToUpdate = k;
  64.         while (indexToUpdate > 0 && GetBitPositionByNr(combination, indexToUpdate)>= n - k + indexToUpdate)
  65.             indexToUpdate--;
  66.  
  67.         if (indexToUpdate == 1) change = 1; // move all bites to the left by one position
  68.         if (indexToUpdate <= 0) break; // done
  69.  
  70. 		 // update combination indices
  71.  
  72. 		new_combination = 0;
  73.         for (int combIndex = GetBitPositionByNr(combination, indexToUpdate) - 1; indexToUpdate <= k; indexToUpdate++, combIndex++)
  74.         {
  75.         	if(change)
  76.         	{
  77.         		new_combination |= (1 << (combIndex + 1));
  78.         	}
  79.         	else
  80.         	{
  81. 	        	combination = combination & (~(1 << combIndex));
  82. 	            combination |= (1 << (combIndex + 1));
  83.         	}
  84.         }
  85.         if(change) combination = new_combination;
  86. 	    change = 0;
  87.     }
  88.  
  89.     int final = 0;
  90.  
  91. 	for(int i = n - 1; i >= k; --i) final += (1 << i);
  92. 	cout << "Final " << final << endl;
  93. 	unsigned int v = (1 << k) - 1; // current permutation of bits 
  94. 	unsigned int w = 0; // next permutation of bits
  95.  
  96. 	do
  97. 	{
  98. 		unsigned int t = (v | (v - 1)) + 1;  
  99. 		w = t | ((((t & -t) / (v & -v)) >> 1) - 1);  
  100. 		v = w;
  101.  
  102. 		cout << "comb bit: " << v << endl;
  103. 	} while(w != final)
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111. 	return 0;
  112. }
Compilation error #stdin compilation error #stdout 0s 3140KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:111:2: error: expected ';' before 'return'
  return 0;
  ^
stdout
copy 
Standard output is empty
https://ideone.com/Z7tB0j
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!