it's a problem similar to determine all possible combinations
One reason of why hypercube still interests computer science or applied mathematic people is its perfect correspondence between the binary system. For example, how many nodes in a d-dimensional hypercube? the answer is quite simple that 2 to the power of d.

Okey, let us back to the main problem today. We want to find all neighbors of node 0 with a given distance. The solution is very easy in concept. Since the distance of two nodes is their Hamming distance, the number of different bits between their node addresses. If we want to find the neighbors with distance k, where k < d, we can just list the nodes with k 1s in their addresses...

We use Sn to denote a set contains all neighbors. The first question is that how many nodes in Sn? Yes, it is a combination of (d, k). To choose k positions for "1" in total d bits. Next question is that how do we list them all by programs?

A recursive technique is needed for this purpose. I would like to thank my younger classmates Dieter for helping me solve this problem. So I share the code (in C++) on the web for anyone who also interested in it.


petitming 發表在 痞客邦 留言(0) 人氣()