Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2001
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2001

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

Search the Archive

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>
  • 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