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>