Enumeration of autocorrelations of length n

enum.cpp

// Mivik 2021.1.24
// Inspired by the predicate given in "Periods in Strings" by Guibas and Odlyzko
// See Leo J. Guibas and Andrew M. Odlyzko. Periods in strings. J. of Combinatorial Theory series A, 30:19–42, 1981.

// Enumerated all autocorrelations for n = 400 in less than 30 seconds on my computer (without writing it to file)
// It DOES REQUIRE A LOT OF TIME AND DISK SPACE to save these autocorrelations, please notice
// For example, for n = 200, it could produce a file up to 200MB
#include <algorithm>
#include <bitset>
#include <iostream>

const int n = 200;

typedef std::bitset<n> bit_vector;

std::vector<bit_vector> rec;
int req[n];
inline int gcd(int x, int y) { while (x %= y) std::swap(x, y); return y; }
void dfs(int o, int lst) {
	static bit_vector vec;

	const int n = ::n - o;
	if (!n) {
		rec.push_back(vec);
		if (!(rec.size() % 100000))
			std::cerr << rec.size() << " computed\n";
		return;
	}
	int *req = ::req + o; // ATTENTION!!! name shadowing for convenience
	vec.set(o);
	for (int p = 1; p < n; ++p) { // enumerate the minimum non-zero period
		if (p >= lst || p > (n - lst) + gcd(lst, p)) {
			if (p * 2 <= n) { // a small period
				const int r = p * (n / p - 1);
				bool ok = true;
				for (int i = 1; i < r; ++i) // check whether it satisfies previous requirements
					if (req[i] && i % p) { ok = false; break; }
				if (ok) {
					for (int i = 1; i < r; ++i) vec.reset(o + i);
					for (int i = p; i < r; i += p) vec.set(o + i);
					if (r + p != n) ++req[r + p]; // requirements might overlap so we use int instead of bool
					dfs(o + r, p);
					if (r + p != n) --req[r + p];
				}
			} else {
				vec.set(o + p);
				dfs(o + p, 0);
			}
		}
		if (req[p]) return;
		vec.reset(o + p);
	}
	// no period exists
	dfs(::n, 0);
}
int main() {
	freopen("autocorrelations.txt", "w", stdout);
	dfs(0, 0);
	std::cerr << "Computation completed, writing to file..." << std::endl;
	std::cout << "Showing " << rec.size() << " autocorrelations for n = " << n << std::endl;

	std::reverse(rec.begin(), rec.end()); // so it's sorted lexicographically
	for (const auto &c : rec) {
		std::cout << '|';
		for (int i = 0; i < n; ++i) std::cout << " o"[c[i]];
		std::cout << "|\n"; // use newline char instead of std::endl to avoid frequent flushing
	}
}