1 #if !defined HAVE_COMBINATION_REVDOOR_H__ 2 #define HAVE_COMBINATION_REVDOOR_H__ 3 // This file is part of the FXT library. 4 // Copyright (C) 2010, 2012, 2013, 2014, 2018, 2019 Joerg Arndt 5 // License: GNU General Public License version 3 or later, 6 // see the file COPYING.txt in the main directory. 7 8 9 #include "fxttypes.h" 10 //#include "jjassert.h" 11 #include "comb/comb-print.h" 12 13 14 class combination_revdoor 15 // Combinations (n choose k) in minimal-change order. 16 // "Revolving door" algorithm following Knuth. 17 // See: 18 // W. H. Payne, F. M. Ives: "Combination Generators", 19 // ACM Transactions on Mathematical Software (TOMS), 20 // vol.5, no.2, pp.163-172, June-1979. 21 { 22 public: 23 ulong *c_; // delta set 24 ulong n_, k_; // (n choose k) n>=1, 1<=k<=n 25 26 combination_revdoor(const combination_revdoor&) = delete; 27 combination_revdoor & operator = (const combination_revdoor&) = delete; 28 29 public: combination_revdoor(ulong n,ulong k)30 explicit combination_revdoor(ulong n, ulong k) 31 // Must have: 1 <= k <= n 32 { 33 n_ = n; // (n ? n : 1); 34 k_ = k; 35 // if ( k>n_ ) k=n; 36 // else { if ( k==0 ) k=n; } 37 38 c_ = new ulong[k_+1]; // incl. sentinel 39 first(); 40 } 41 ~combination_revdoor()42 ~combination_revdoor() { delete [] c_; } 43 first()44 void first() 45 { 46 for (ulong j=0; j<k_; ++j) c_[j] = j; 47 c_[k_] = n_; // sentinel 48 } 49 data()50 const ulong* data() const { return c_; } 51 next()52 bool next() 53 { 54 ulong j = 1; 55 // R3: [Easy case?] 56 if ( k_ & 1 ) // odd k (try to increase) 57 { 58 ulong c = c_[0] + 1; 59 if ( c < c_[1] ) { c_[0] = c; return true; } 60 else goto R4; 61 } 62 else // even k (try to decrease) 63 { 64 ulong c = c_[0]; 65 if ( c ) { c_[0] = c-1; return true; } 66 else goto R5; 67 } 68 69 R4: // R4: [Try to decrease] 70 if ( j==k_ ) return false; 71 72 // jjassert( c_[j] == c_[j-1]+1 ); 73 if ( c_[j] > j ) 74 { 75 c_[j] = c_[j-1]; 76 c_[j-1] = j-1; 77 return true; 78 } 79 ++j; 80 81 R5: // R5: [Try to increase] 82 if ( j==k_ ) return false; 83 84 // jjassert( c_[j-1] == j-1 ); 85 { 86 ulong c = c_[j] + 1; 87 if ( c < c_[j+1] ) // can read sentinel 88 { 89 c_[j-1] = c - 1; 90 c_[j] = c; 91 return true; 92 } 93 } 94 ++j; 95 goto R4; 96 } 97 98 void print_set(const char *bla=nullptr) const 99 { ::print_set(bla, c_, k_); } 100 101 void print_deltaset(const char *bla=nullptr) const 102 { print_set_as_deltaset(bla, c_, k_, n_); } 103 }; 104 // ------------------------- 105 106 107 #endif // !defined HAVE_COMBINATION_REVDOOR_H__ 108