       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

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:= InputForm[cartesianSet]
Out//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:= hammingDistance[5,11]
Out= 3

Daniel Lichtblau
Wolfram Research

```

• References:
• Backtrack