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 n){
  12.     uint32_t t = (n | (n - 1)) + 1;
  13.     return t | ((((t & -t) / (n & -n)) >> 1) - 1);
  14. }
  15.  
  16.  
  17. int sumIndices(uint32_t n){
  18.     const int MultiplyDeBruijnBitPosition[32] = {
  19.       0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  20.       31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  21.     };
  22.  
  23.     int sum = 0;
  24.     do sum += MultiplyDeBruijnBitPosition[((uint32_t)((n & -n) * 0x077CB531U)) >> 27];
  25.     while (n &= n-1);
  26.  
  27.     return sum;
  28. }
  29.  
  30.  
  31. int main(){
  32.     uint32_t n,  // bit set
  33.              k,  // sum of indicies
  34.              p,  // current permutation
  35.              lp; // final permutation
  36.  
  37.     std::cin >> k;
  38.     std::cin >> n;
  39.  
  40.     p = firstPermutation(n);
  41.     lp = lastPermutation(n);
  42.  
  43.     do {
  44.         p = nextPermutation(p);
  45.         if (sumIndices(p) == k){
  46.             std::cout << "p:" << p << std::endl;
  47.         }
  48.     } while(p != lp);
  49.  
  50.     return 0;
  51. }
  52.  
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
22
2
stdout
copy 
p:5120
p:8704
p:16640
p:32896
p:65600
p:131104
p:262160
p:524296
p:1048580
p:2097154
p:4194305
https://ideone.com/263IfL
Anroca - solution for https://stackoverflow.com/questions/62878331
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!