|
(C++)
#include <iostream>
#include <vector>
// DFS for binary de Bruijn graph. Count cycles starting at start, and
// don't visit cycles with nodes v < start, to avoid double counting
// any cycle.
uint64_t cycles_visit(uint64_t mask, uint64_t start, uint64_t v, std::vector<char>& visited) {
visited[v] = true;
const uint64_t neighbors[2] = { (v << 1) & mask, ((v << 1) & mask) | 1 };
uint64_t count = 0;
for(uint64_t n : neighbors) {
if(n < start) continue;
if(visited[n]) {
if(n == start)
++count;
} else {
count += cycles_visit(mask, start, n, visited);
}
}
visited[v] = false;
return count;
}
int main(int argc, char *argv[]) {
if(argc != 2) {
std::cerr << "Usage: " << argv[0] << " k\n";
return 1;
}
const unsigned k = std::atoi(argv[1]);
const uint64_t mask = ((uint64_t)1 << k) - 1;
if(k == 1) { // Optimization below does not work for k==1
std::cout << 3 << '\n';
return 0;
}
std::vector<char> visited(mask+1, false);
// Cycles starting with 0...01
uint64_t total = cycles_visit(mask, 1, 1, visited);
// Cycles containing 0...0 also contain 0...01, except for the self loop 0...0
total += total + 1;
// Start from all other nodes
for(uint64_t v = 2; v < mask; ++v) {
total += cycles_visit(mask, v, v, visited);
}
total += 1; // self loop 1...1
std::cout << total << '\n';
return 0;
}
(Python)
import networkx as nx
def deBruijn(n): return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))
| 