Talk:De Bruijn sequence

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Start Class	Low Priority	Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Geometry guy 21:11, 1 June 2007 (UTC)

to create a de-bruijn sequance, "find an Eularian cycle on a de-bruijn graph" is wrong, because Eularian cycle has to use every "edge" once, but to create a de-bruijn sequance need to use every "node" once on a de-bruijn graph.

the article is correct and you are wrong, 'to create a de-bruijn sequance need to use every "node" once on a de-bruijn graph' is incorrect.

I think that the article, which now says "by taking an Hamiltonian cycle of a complete graph of order kⁿ", is wrong. A Hamiltonian cycle over the complete graph is just an ordering of the kⁿ sequences, but since only some orderings give a de Bruijn sequence, this is meaningless. It should rather say "by taking a Hamiltonian cycle of an n-dimensional de Bruijn graph over k symbols. Am I wrong? --fudo 14:29, 10 July 2006 (UTC)

I was wondering the same thing. Since no-one else seems to have objected here over the past 2+ months, I'll be bold and commit it. —JLD 20:31, 28 September 2006 (UTC)

As I understand it, you do use every EDGE exactly once. Michael Hardy 22:26, 28 September 2006 (UTC)

... and now I've added a diagram and an accompanying explanation of why it's Eulerian and not Hamiltonian. Michael Hardy 23:43, 28 September 2006 (UTC)

Everything you said is correct, except for that "not". In fact, by following an Eulerian cycle over an n-dimensional de Bruijn graph, you obtain a de Bruijn sequence of order n + 1. Since it's easy to prove (by the definition) that the n + 1-dimensional de Bruijn graph is just the line graph of the n-dimensional one, an Eulerian cycle over the first corresponds exactly to a Hamiltonian cycle over the second one. Try it by yourself. I'll modify slightly the article, leaving your example (which is perfect) as is. --fudo 13:05, 4 October 2006 (UTC)

The early on sentence: "Taking A = {0,1}, there are two distinct B(2,3): 00010111 and 00011101, one being the reverse of the other." Those two sequences are not the reverse of each other. Either a) this should say there are 4 distinct, 00010111 and 00011101 and these two reversed, which appears correct to me or b.) the part about "one being the reverse of the other" should be taken out. 17:18, 5 November 2006 (UTC)

They are reverses of each other if you mod out by cyclic shifts. Michael Hardy 20:15, 6 November 2006 (UTC)

The initial example given (A={0,1}) does not contain the subsequence 110 (although its claimed "reverse" does). So what's going on?

Oh never mind -- it is cyclic, so the sequence is "properly" viewed including the wrap-around from back to front. So the initial B(2,3) contains 110 via the "final" ones + the "initial" zero.

I think the use of the term "subsequence" in the first paragraph is wrong. It should be changed into "substring" or something (Mathworld sais "subrange"), since the elements of a subsequence need not be consecutive in the original sequence. —Preceding unsigned comment added by 85.73.195.2 (talk) 12:27, 16 December 2007 (UTC)

[edit] Capitals

Why is "de Bruijn sequence" not written as "De Bruijn sequence", with capital D? At least in Dutch, the first character of a name has to be a capital, even if it is something like "de" or "van" (so meneer (mister) De Bruijn, but Nicolaas Govert de Bruijn) and I never learned that that's different in English. And after all, De Bruijn was a Dutchman.DaanAlberga 13:15, 8 June 2006 (UTC)

Then why is the initial d in lower case at [[1]]? Michael Hardy 23:52, 12 June 2006 (UTC)

The initial d only is in lower case when it is _not_ the first letter of his name. In "a de Bruijn sequence", the d _is_ the initial letter of his name. In your reference, the Dutch page about De Bruijn, one can see that as well. When it says "Nicolaas de Bruijn" or something like that, the d is in lower case, and when it just says "De Bruijn", the d is a capital. DaanAlberga 09:31, 13 June 2006 (UTC)

[edit] Possitional encoding improvements

For a flat (not wraped application of possitional detection. Arrange for the sequence of zeros to be at one end and ones at the other. i.e. for the sequence from the article 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 change the point where it would but does not wrap so the sequence reads. 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0

Now you can extend the sequence with e.g. (1 1 1 1 1...) 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 (0 0 0 0 0...) Now if the senser detects it is in an all zero or all one regon it knows it is off the map and in which direction. Note: not worked things out for a 2d map but, if in corners it has a 50% chance of getting one axis incorrect, the corect axis will get it out of the corner where it will head back to the map.

—Preceding unsigned comment added by 204.193.45.69 (talk) 16:50, 11 January 2008 (UTC)