Hamming Distance problem

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Hamming Distance problem

Hi,

I've been set an assignment to find the maximum hamming distance between 2 nodes for level i. I'm having some trouble mainly because I don't understand what a level is. Could anyone help me out?
Chironic

Posts: 7
Joined: Sat Nov 20, 2010 2:49 pm UTC
Location: Glasgow, Scotland

Re: Hamming Distance problem

You might want to actually copy the question.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk
Poster with most posts but no title.

Posts: 10211
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Hamming Distance problem

The question is actually "find the maximum hamming distance between two vertices at level i of an n-cube, where the level of a vertex in an n-cube is the number of 1s in the coordinate description of the cube, where the vertices are elements of {0,1}^n, connected in the obvious way."

One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk
Poster with most posts but no title.

Posts: 10211
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Hamming Distance problem

Sorry, yes it's for an n-cube. I just don't understand the "level" part
Chironic

Posts: 7
Joined: Sat Nov 20, 2010 2:49 pm UTC
Location: Glasgow, Scotland

Re: Hamming Distance problem

Huh, that seems pretty trivial.

For a 2-cube, you've got the four vertices (0,0), (0,1), (1,0), and (1,1). According to the definition in Yakk's post, the levels are respectively 0, 1, 1, and 2, because that's the number of 1s in each vertex.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 4142
Joined: Tue Feb 20, 2007 12:49 am UTC

Re: Hamming Distance problem

Xanthir wrote:For a 2-cube, you've got the four vertices (0,0), (0,1), (1,0), and (1,1). According to the definition in Yakk's post, the levels are respectively 0, 1, 1, and 2, because that's the number of 1s in each vertex.
Yep.
Huh, that seems pretty trivial.
Yep.
Chironic wrote:Sorry, yes it's for an n-cube. I just don't understand the "level" part
What part of the description I just posted of what level means wasn't clear?

Do you understand what "{0,1}^n as coordinates of the vertices of an n-cube" means?

Do you understand what Rn means? Same thing, but where the elements of the vector are 0 or 1, and not all of R.

Do you understand "The level of the vertex is the number of 1s"?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk
Poster with most posts but no title.

Posts: 10211
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Hamming Distance problem

So basically it's the number of 1s in A XOR B?
cjmcjmcjmcjm wrote:If it can't be done in an 80x24 terminal, it's not worth doing
Meem1029

Posts: 378
Joined: Wed Jul 21, 2010 1:11 am UTC

Re: Hamming Distance problem

Meem1029 wrote:So basically it's the number of 1s in A XOR B?

Yes. The treatment I'm familiar with defines strings to be elements of C^n where n is max string length and C is the field of integers modulo 2. From here the norm |.| is defined to be the number of 1s in the string, and the metric is naturally given as d(x,y) = |x-y| which is the how we extend the Euclidian norm to the usual distance function. Another way to think of it is as the number of places in which the two strings differ, so say d(0010,1010) = 1 and d(1111,1010) = 2 just by inspection on where the are not the same. Simple enough to calculate with.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

Cleverbeans

Posts: 1180
Joined: Wed Mar 26, 2008 1:16 pm UTC