如何生成Chase的序列

Question

在計算機編程領域的第7.2.1.3節草案中，生成所有組合，Knuth引入了用於生成Chase序列的算法C.

他也提到了類似的算法（根據下面的公式）和索引列表的工作沒有源代碼（草案行使45）。

我終於想出了一個C++版本我認爲這是相當難看。生成所有C_N^M組合，存儲複雜性是約3（M + 1）和時間複雜性爲O（MN^M）

class chase_generator_t{ 
public: 
    using size_type = ptrdiff_t; 
    enum class GET : char{ VALUE, INDEX }; 

    chase_generator_t(size_type _n) : n(_n){} 
    void choose(size_type _m){ 
     m = _m; 
     ++_m; 
     index.resize(_m); 
     threshold.resize(_m + 1); 
     tag.resize(_m); 
     for (size_type i = 0, j = n - m; i != _m; ++i){ 
      index[i] = j + i; 
      tag[i] = tag_t::DECREASE; 
      using std::max; 
      threshold[i] = max(i - 1, (index[i] - 3) | 1); 
     } 
     threshold[_m] = n; 
    } 
    bool get(size_type &x, size_type &y, GET const which){ 
     if (which == GET::VALUE) return __get<false>(x, y); 
     return __get<true>(x, y); 
    } 
    size_type get_n() const{ 
     return n; 
    } 
    size_type get_m() const{ 
     return m; 
    } 
    size_type operator[](size_t const i) const{ 
     return index[i]; 
    } 
private: 
    enum class tag_t : char{ DECREASE, INCREASE }; 
    size_type n, m; 
    std::vector<size_type> index, threshold; 
    std::vector<tag_t> tag; 

    template<bool GetIndex> 
    bool __get(size_type &x, size_type &y){ 
     using std::max; 
     size_type p = 0, i, q; 
    find: 
     q = p + 1; 
     if (index[p] == threshold[q]){ 
      if (q >= m) return false; 
      p = q; 
      goto find; 
     } 
     x = GetIndex ? p : index[p]; 
     if (tag[p] == tag_t::INCREASE){ 
      using std::min; 
     increase: 
      index[p] = min(index[p] + 2, threshold[q]); 
      threshold[p] = index[p] - 1; 
     } 
     else if (index[p] && (i = (index[p] - 1) & ~1) >= p){ 
      index[p] = i; 
      threshold[p] = max(p - 1, (index[p] - 3) | 1); 
     } 
     else{ 
      tag[p] = tag_t::INCREASE; 
      i = p | 1; 
      if (index[p] == i) goto increase; 
      index[p] = i; 
      threshold[p] = index[p] - 1; 
     } 
     y = index[p]; 
     for (q = 0; q != p; ++q){ 
      tag[q] = tag_t::DECREASE; 
      threshold[q] = max(q - 1, (index[q] - 3) | 1); 
     } 
     return true; 
    } 
}; 

沒有任何一個具有更好的實施方案，即有界跑得更快使用相同的內存或以相同的速度使用較少的內存？

Answer 1

我認爲下面的C代碼更接近Knuth的想法。毫無疑問，有些方法可以使它更加優雅（特別是，我留下一些腳手架以防實驗），儘管我懷疑陣列w可以處置。如果由於某種原因存儲非常重要，則從a陣列中竊取符號位。

#include <stdbool.h> 
#include <stdio.h> 

enum { 
    N = 10, 
    T = 5 
}; 

static void next(int a[], bool w[], int *r) { 
    bool found_r = false; 
    int j; 
    for (j = *r; !w[j]; j++) { 
    int b = a[j] + 1; 
    int n = a[j + 1]; 
    if (b < (w[j + 1] ? n - (2 - (n & 1)) : n)) { 
     if ((b & 1) == 0 && b + 1 < n) b++; 
     a[j] = b; 
     if (!found_r) *r = j > 1 ? j - 1 : 0; 
     return; 
    } 
    w[j] = a[j] - 1 >= j; 
    if (w[j] && !found_r) { 
     *r = j; 
     found_r = true; 
    } 
    } 
    int b = a[j] - 1; 
    if ((b & 1) != 0 && b - 1 >= j) b--; 
    a[j] = b; 
    w[j] = b - 1 >= j; 
    if (!found_r) *r = j; 
} 

int main(void) { 
    typedef char t_less_than_n[T < N ? 1 : -1]; 
    int a[T + 1]; 
    bool w[T + 1]; 
    for (int j = 0; j < T + 1; j++) { 
    a[j] = N - (T - j); 
    w[j] = true; 
    } 
    int r = 0; 
    do { 
    for (int j = T - 1; j > -1; j--) printf("%x", a[j]); 
    putchar('\n'); 
    if (false) { 
     for (int j = T - 1; j > -1; j--) printf("%d", w[j]); 
     putchar('\n'); 
    } 
    next(a, w, &r); 
    } while (a[T] == N); 
}