Skip to content

Instantly share code, notes, and snippets.

@Mivik
Created Jan 27, 2021
Embed
What would you like to do?
Enumeration of autocorrelations, along with their populations.
// 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 <cassert>
#include <cstdint>
#include <iostream>
const int $n = 60;
const int C = 2;
int n;
struct bit_vector {
int v[2];
inline bool test(int i) const { return v[i >> 5] & (1 << (i & 31)); }
inline void set(int i) { v[i >> 5] |= 1 << (i & 31); }
inline void reset(int i) { v[i >> 5] &= ~(1 << (i & 31)); }
inline void reset() { v[0] = v[1] = 0; }
inline bool contains(const bit_vector &t) const { return (v[0] & t.v[0]) == t.v[0] && (v[1] & t.v[1]) == t.v[1]; }
};
struct info {
bit_vector vec;
int nfc;
uint64_t pop;
info(bit_vector vec, int nfc, uint64_t pop):
vec(std::move(vec)), nfc(nfc), pop(pop) {}
};
bit_vector vec;
std::vector<info*> rec;
int req[$n];
inline uint64_t qpow(uint64_t x, int p) {
uint64_t ret = 1;
for (; p; p >>= 1, x *= x) if (p & 1) ret *= x;
return ret;
}
inline int gcd(int x, int y) { while (x %= y) std::swap(x, y); return y; }
void dfs(int o, int lst, int cnt) {
const int n = ::n - o;
if (!n) {
uint64_t pop = qpow(C, cnt);
for (size_t i = rec.size() - 1; ~i; --i) {
const auto &info = rec[i];
if (info->vec.contains(vec)) pop -= info->pop;
}
rec.push_back(new info(vec, cnt, pop));
if (!(rec.size() % 10000))
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, cnt);
if (r + p != n) --req[r + p];
}
} else {
vec.set(o + p);
dfs(o + p, 0, cnt + (p << 1) - n);
}
}
if (req[p]) return;
vec.reset(o + p);
}
// no period exists
dfs(o + n, 0, cnt + n);
}
int main() {
freopen("autocorrelations.txt", "w", stdout);
for (n = 1; n <= $n; ++n) {
dfs(0, 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 (auto info : rec) {
std::cout << '|';
for (int i = 0; i < n; ++i) std::cout << " o"[info->vec.test(i)];
std::cout << "| " << info->pop << '\n'; // use newline char instead of std::endl to avoid frequent flushing
delete info;
}
vec.reset(); rec.clear();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment