这是我在Sawada和Ruskey的论文中对图1中算法的C
++实现：
void debruijn(unsigned int t, unsigned int p, const unsigned int k, const unsigned int n, unsigned int* a, boost::function<void (unsigned int*,unsigned int*)> callback){ if (t > n) { // we want only necklaces, not pre-necklaces or Lyndon words if (n % p == 0) { callback(a+1, a+p+1); } } else { a[t] = a[t-p]; debruijn(t+1, p, k, n, a, callback); for (unsigned int j = a[t-p]+1; j < k; ++j) { a[t] = j; debruijn(t+1, t, k, n, a, callback); } }}struct seq_printer { const std::vector<char>& _alpha; seq_printer(const std::vector<char>& alpha) : _alpha(alpha) {} void operator() (unsigned int* a, unsigned int* a_end) const { for (unsigned int* i = a; i < a_end; ++i) { std::cout << _alpha[*i]; } }};...std::vector<char> alpha;alpha.push_back('a');alpha.push_back('b');alpha.push_back('c');unsigned int* a = new unsigned int[N+1];a[0] = 0;debruijn(1, 1, alpha.size(), N, a, seq_printer(alpha));if (N > 1) std::cout << alpha[0];std::cout << std::endl;delete[] a;The full reference for the paper is: Joe Sawada and Frank Ruskey, “An
Efficient Algorithm for Generating Necklaces with Fixed Density”, SIAM Journal
of Computing 29 :671-684, 1999.
