fork download
copy 
  1. #include <iostream>
  2.  
  3. uint32_t firstPermutation(uint32_t &p){
  4.     return (1 << p) -1;
  5. }
  6.  
  7. uint32_t lastPermutation(uint32_t &p){
  8.     return (0xFFFFFFFF >> p) ^ 0xFFFFFFFF;
  9. }
  10.  
  11. uint32_t nextPermutation(uint32_t &p){
  12.     uint32_t t = (p | (p - 1));
  13.     return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(p) + 1));
  14. }
  15.  
  16. int sumIndices(uint32_t n){
  17.     int sum = 0;
  18.     do sum += __builtin_ctz(n);
  19.     while (n &= n-1);
  20.     return sum;
  21. }
  22.  
  23. int main(int argc, char **argv){
  24.     uint32_t n,  // bit set
  25.              k,  // sum of indicies
  26.              p,  // current permutation
  27.              lp; // final permutation
  28.  
  29.  
  30.     std::cin >> k;
  31. 	std::cin >> n;
  32.  
  33. 	//k = std::atoi(argv[1]);
  34.     //n = std::atoi(argv[2]);
  35.  
  36.     p = firstPermutation(n);
  37.     lp = lastPermutation(n);
  38.  
  39.     do {
  40.         p = nextPermutation(p);
  41.         if (sumIndices(p) == k){
  42.             std::cout << p << std::endl;
  43.         }
  44.     } while(p != lp);
  45.  
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0s 4492KB
comments (?)
stdin
copy 
22
2
stdout
copy 
5120
8704
16640
32896
65600
131104
262160
524296
1048580
2097154
4194305
https://ideone.com/dILgpB
Anroca - https://stackoverflow.com/a/62976406/5496117
language:
C++14 (gcc 8.3)
created:
5 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!