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