Re: Backtrack
- To: mathgroup at smc.vnet.net
- Subject: [mg31912] Re: [mg31848] Backtrack
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 11 Dec 2001 01:33:50 -0500 (EST)
- References: <200112071056.FAA10554@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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
- References:
- Backtrack
- From: Chekad Sarami <csarami@mtu.edu>
- Backtrack