debruijn

debruijn.c (1738B)

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdarg.h>

/* De Bruijn sequence generation based on Burrows-Wheeler transform */

static void
die(const char *fmt, ...)
{
	va_list ap;

	va_start(ap, fmt);
	fprintf(stderr, "debruijn: ");
	vfprintf(stderr, fmt, ap);
	if (*fmt && fmt[strlen(fmt)-1] == ':') {
		fputc(' ', stderr);
		perror(NULL);
	} else {
		fputc('\n', stderr);
	}
	va_end(ap);

	exit(1);
}

static void
gen(bool *visited, const char *alph, size_t k, size_t n, size_t len, size_t cnt)
{
	size_t i, si, so, plen, out;

	plen = len / k;
	out = 0;
	memset(visited, 0, len);
	for (i = 0; i < len; i++) {
		if (visited[i]) continue;
		so = i;
		do {
			si = so;

			putchar(alph[si / plen]);
			if (++out == cnt) return;
			visited[si] = true;

			/* (sorted -> unsorted) translation */
			so = (si % plen) * k + si / plen;
		} while (!visited[so]);
	}
}

int
main(int argc, const char **argv)
{
	const char **arg;
	const char *alph_arg, *n_arg;
	size_t i, k, n, len;
	bool all, *visited;

	all = false;
	alph_arg = n_arg = NULL;
	for (arg = argv + 1; *arg; arg++) {
		if (!strcmp(*arg, "-h") || !strcmp(*arg, "--help")) {
			break;
		} else if (!strcmp(*arg, "-a")) {
			all = true;
		} else if (!alph_arg) {
			alph_arg = *arg;
		} else if (!n_arg) {
			n_arg = *arg;
		} else {
			break;
		}
	}

	if (*arg || !alph_arg || !n_arg) {
		fprintf(stderr, "Usage: debruijn ALPH N\n");
		return 1;
	}

	k = strlen(alph_arg);
	n = strtoull(n_arg, NULL, 10);
	if (!k || !n) die("invalid args");

	for (len = 1, i = 0; i < n; i++) len *= k;
	visited = malloc(len);
	if (!visited) die("malloc:");

	gen(visited, alph_arg, k, n, len, len);
	if (all) gen(visited, alph_arg, k, n, len, k - 1);
}