MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Backtrack


Chekad Sarami wrote:
> 
> I hope somebody still working and can help me.I appreciate if you can
> help for the following:
> 
> 1) how can I define {0,1}^n (Cartisian product) in mathematica?
> 2) How can I define the hamming distance( dist(x,y) or hamming distance
> between x,y in {0,1}^n) between codes
> 3) non-linear code of length n and minimum distace d i a subest C of
> {0,1}^n such that dist(x,y)>=d for all x,y in C.
> 
> Actually, I am going to use Backtrack Command in mathematica to compute
> the maximum number of n-tuples in length n non-linear code of minimum
> distance d Denoted by A(n,d). I just want to compute A(8,4).
> 
> Many thanks
> CHEKAD

This may help to get started. The first will get you all {0,1} tuples of
length n.

cartesianSet[n_] := Map[IntegerDigits[#,2,n]&, Range[0,2^n-1]]

Example:
In[53]:= InputForm[cartesianSet[3]]
Out[53]//InputForm= 
{{0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1,
1, 0}, 
 {1, 1, 1}}

For Hamming distance you could work with the representation above as
list of {),1} bits but it is more efficient to work directly on integers
regarded as lists bits.

hammingDistance[i1_, i2_] := DigitCount[BitXor[i1,i2],2,1]

Example:
In[54]:= hammingDistance[5,11]
Out[54]= 3


Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: Trouble with Splice for Java (i.e. there is no JForm)
  • Next by Date: Re: Simple Eval Question
  • Previous by thread: Backtrack
  • Next by thread: photonic band gaps