Author: Gerd Isenberg
Date: 03:41:47 06/17/04
Go up one level in this thread
I found this more general De Bruijn generator from Jean-Paul Davalan in the net.
http://perso.wanadoo.fr/jean-paul.davalan/divers/debruijn/debruijn.c.txt
It works with char strings and other alphabets too, and it confirms the number
for binary 64-bit sequences of 2**26.
The produced sequences are the even ones of mine algorithm.
The output is reserved (may be easyly changed). It took about five minutes (P4
2GHz) for the following run to count the 2**26 64-sequences of the alphabet
"01".
It is recursive too, but until now i did not understand it completely.
I found mine one much more intuitive, may be due to some similarities to a
recursive search routine ;-)
Whether it is possible to gain much more speed if using binary bitboard
representation, rather than pre-allocated char strings for that special purpose
is the question. So i guess from algorithm perspective it is not faster than
mine and still much too slow ;-(
Gerd
D:>deBruijnGen 6 01
# De Bruijn sequences
# letters 6 alphabet "01"
# Word length 64
# 67108864 sequences
/* debruijn.c
*
* finds De Bruijn sequences : debruijn 3 abcd
* cc -o debruijn debruijn.c
* Jean-Paul Davalan © 2000 2001 2002
* jpdvl@wanadoo.fr
*
* Licence GPL
* GPL license
*
* BUGS :
* limitation due à la récursivité
* (et non un problème d'allocation mémoire du programme C)
*/
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#define MAXNS 200000
typedef unsigned int uint;
uint num = 0, /* # sequences */
*C, /* De Bruijn sequence */
N, /* word length */
P, /* alphabet length */
M, NS; /* # words NS = P^N, M = P^(N-1) */
char *W, /* words, vertices (ham.) edges (Euler) */
*A; /* alphabet */
void next(uint n, uint i)
{ /* next word */
uint j, k, r, s;
r = n / P;
C[i] = n / M, W[n] = (char)0;
if (i < NS - 1) {
for (k = 0; k < P; k++) {
s = r + k * M;
if (W[s]) next(s, i + 1);
}
} else {
num++;
#if 0 // only count
for (j = 0; j < NS; j++)
printf("%c", A[C[j]]);
printf("\n");
exit(0); // only one
#endif
}
W[n] = (char)1;
}
int main(int argc, char *argv[])
{
uint i;
if (argc < 3)
printf("usage: debruijn wordlen alphabet\n"), exit(0);
N = atoi(argv[1]), P = strlen(argv[2]), A = argv[2];
for (NS = 1, i = 0; i < N && NS <= MAXNS; NS *= P, i++);
if (i < N-1 || NS > MAXNS) printf("too long\n"), exit(1);
M = NS / P;
printf("# De Bruijn sequences\n# letters %d alphabet \"%s\"\n", N, A);
printf("# Word length %d\n", NS);
if ((W = (char *)malloc(NS * sizeof(char))) == NULL)
printf("malloc 1 fails\n"), exit(1);
memset((void *)W, (char)1, NS);
for (i = 0; i < NS; W[i]=(char)1, i++);
if ((C = (uint *) malloc(NS * sizeof(uint))) == NULL)
printf("malloc 2 fails\n"), exit(1);
next(0, 0);
printf("# %d sequences\n",num);
return 0;
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.