## Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other

I’m working on a system that will require manual data entry of 10-digit numbers (Σ = 0123456789). To help prevent data errors, I want to avoid generating any two strings that have a hamming distance of 1.

For example, if I generate the string 0123456789 then I never want to generate any of these strings: {1123456789, 2123456789, 3123456789, …}

What is the largest set of unique strings in the universe of possible strings that satisfy the constraint where no two strings have a hamming distance of 1? If this set can be identified, is there any reasonable way to enumerate it?

Posted on Categories proxies

## RC-Code if I have a generator matrix for a specific code how do I get the distance to the dual code?

$$\mathcal{R} \mathcal{S}_{6, 3}$$ and $$a_{i} \in \mathbb{F}_{11}$$

G=$$\begin{pmatrix}1&1&1 &1&1&1\ 0&1&2 &3&4&5\ 0&1^2&2^2 &3^2&4^2&5^2 \end{pmatrix}$$

G=$$\begin{pmatrix} 1&1&1 &1&1&1\0&1&2 &3&4&5\ 0&1&4 &9&5&3 \end{pmatrix}$$

I now have to determine the distance to the dual code.

Any clue how to accomplish this?

Thanks for any help.

Posted on Categories proxies

## Is there a name for the class of distance functions that are compatible with k-d trees?

The typical nearest neighbor search implementation for k-d trees prunes branches when the distance between the target and the pivot along the current axis exceeds the smallest distance found so far. This is correct (doesn’t wrongly prune any points) for any Minkowski distance. Is there a broader class of well-known distance functions that are compatible? Formally, I think the necessary and sufficient condition is just

$$d(x,y) \ge |x_i – y_i|$$

for $$x, y \in \mathbb{R}^n$$, $$1 \le i \le n$$.

Posted on Categories proxies

## C++ STL: How does the distance() method work for a set/ multiset (stored internally as a self balancing tree)?

I’m working on the problem: Count smaller elements on right side using Set in C++ STL

The solution is to add each element to the set and then to count the elements on the left, the distance function is called.

This is the algo:

1. Traverse the array element from i=len-1 to 0 and insert every element in a set. 2. Find the first element that is lower than A[i] using lower_bound function. 3. Find the distance between above found element and the beginning of the set using distance function. 4. Store the distance in another array Lets say CountSmaller. 4. Print that array 

I’m having a hard time to visualize or understand how can distance function be used with a set like structure since internally, the set data is stored as a self balanced tree (Red Black Tree). Whats the concept of distance for a self balancing tree and how does calling distance() give us the count of smaller elements on the right side?

Posted on Categories proxies

## What is the difference between these two Edit Distance Algorithm

Edit Distance is very well known problem in computer science. Came up with following algorithm after reading through CLRS but it doesn’t work. Check the working algorithm below, I couldn’t find why first algorithm doesn’t work while second one does.

  public int find (String word1, String word2, int i, int j, int count) {     if (i >= word1.length()) return  count + word2.length() - j;     if (j >= word2.length()) return  count + word1.length() - i;      if (dp[i][j] != -1) return dp[i][j];      if (word1.charAt(i) == word2.charAt(j)) {         dp[i][j] = find(word1, word2, i+1, j+1, count);     } else {         int replace = find(word1, word2, i+1, j+1, count + 1);         int delete = find(word1, word2, i+1, j, count + 1);         int insert = find(word1, word2, i, j+1, count + 1);                  dp[i][j] = Math.min(replace, Math.min(delete, insert));     }      return dp[i][j]; } 

Notice, how I’m passing the cost of edit in method argument. Now, the algorithm which works. Here I’m not passing the edit distance in the method parameter instead of I’m adding 1 to recursive method.

  public int find (String word1, String word2, int i, int j) {     if (i >= word1.length()) return  word2.length() - j;     if (j >= word2.length()) return  word1.length() - i;      if (dp[i][j] != -1) return dp[i][j];      if (word1.charAt(i) == word2.charAt(j)) {         dp[i][j]  = find(word1, word2, i+1, j+1, count);     } else {         int replace = find(word1, word2, i+1, j+1, count + 1);         int delete = find(word1, word2, i+1, j, count + 1);         int insert = find(word1, word2, i, j+1, count + 1);                  dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));     }      return dp[i][j]; } 

I’m not able to think why first algorithm fails. Appreciate, if you can point my error in understanding.

Posted on Categories proxies

## Distance to $k$th nearest neighbor efficiently for arbitrary $k$

Problem. Given $$X$$ a finite metric space of cardinality $$n$$, construct a data structure in subquadratic time such that the query distance to the kth nearest neighbor of x can be resolved in sublinear time (independent of $$k$$) for arbitrary $$k \leq n$$ and $$x \in X$$.

What I have tried. I am aware of the existence of kdtrees, ball-trees, and cover trees. Under some assumptions (which I’m willing to make), I know that these structures can resolve the query distance to the nearest neighbor of x in sublinear time (often $$O(\log(n))$$), but I haven’t been able to find similar results for the $$k$$th nearest neighbor for arbitrary $$k$$.

It seems that, often, one is interested in $$k$$ values that are small compared to $$n$$, and that, in those cases, the algorithms mentioned in the previous paragraph can be adapted at the cost of a multiplicative constant of the order of $$k$$. My problem is that I am interested in $$k$$ values that are potentially of the order of $$n$$.

Posted on Categories proxies

## Why is my character disapearing when going north a distance

My character hides behind the floor tiles when i go north far enough. I do not have ysort enabled for the floor tiles. So this shouldn’t happen at all but it does.

Posted on Categories Free Proxy

## Joint typicality and distance between the vectors

In the book by Cover and Thomas,the author says that

We first review the single-user Gaussian channel studied in Chapter 9. P Here Y = X + Z. Choose a rate R < 12 log(1 + N ). Fix a good ($$2^{nR}$$ , n) codebook of power P . Choose an index w in the set $$2^{nR}$$ . Send the wth codeword X(w) from the codebook generated above. The receiver observes Y = X(w) + Z and then finds the index ŵ of the codeword closest to Y. If n is sufficiently large, the probability of error Pr(w $$\neq$$ ŵ) will be arbitrarily small. As can be seen from the definition of joint typ- icality, this minimum-distance decoding scheme is essentially equivalent to finding the codeword in the codebook that is jointly typical with the received vector Y.

I am unable to mathematically see how $$(X^n,Y^n)$$ being jointly weak typical implies that distance between $$X^n$$ and $$Y^n$$ is smaller than other possible $$X^n$$ with which $$Y^n$$ is not typical? The author had proved the capacity using jointly weak typicality.

To be more exact, can someone please how vectors $$(x_1^n,y^n)$$ chosen IID from $$P_{XY}$$ staisfying the first condition satisfies the second: $$\frac{-1}{n}\log \Pr{(x_1^n,y^n)} \approx H(X,Y)$$ $$dist(x_1^n,y^n) < dist(x_k^n,y^n) \forall x_k^n \neq x_1^n$$ and $$x_k \sim P_X$$
The second condition is the minimum distance condition. $$dist()$$ can be any valid measure I guess.

Posted on Categories proxies

## Knock out from a distance

Per the below rules, it looks like that a PC can only knock out a creature when in melee.

Sometimes an attacker wants to incapacitate a foe, rather than deal a killing blow. When an attacker reduces a creature to 0 hit points with a melee attack, the attacker can knock the creature out. The attacker can make this choice the instant the damage is dealt. The creature falls unconscious and is stable.

Is there something I am missing in order to be able to knock a creature from a distance (by a range weapon or a spell for instance). Or this is not doable ? If at the GM discretion : do you usually allow it ? With any specificity ?

## Multiple queries in phpmyadmin – Distance using coordinates, Slope, Intercept, Angle, and few more

I having around 500 excel sheets in .csv format with data captured for my experiment having following columns in place. Now I need to calculate the following parameters using this data. I have done these in excel, however doing this repeatedly for each excel so many times is difficult, so I want to write an SQL query in PhpmyAdmin will help some time.

1. Last charecter typed – need to capture last charecter from the column ‘CharSq’
2. *Slope (in column J) =(B3-B2)/(A3-A2)
3. Intercept (in column K) =B2-(A2*(J3))
4. Angle (in degrees) =MOD(DEGREES(ATAN2((A3-A2),(B3-B2))), 360) –
5. Index of Difficulty =LOG(((E1/7.1)+1),2)
6. Speed Value length (if speed value length >3, then mark as 1 or else 0) = =IF(LEN(D3) >= 3, "1","0")
7. Wrong Sequence (if I3=I2,then mark search time, else actual time) =IF(I3=I2,"Search Time","Actual Time")
8. Mark charecter into (1,2,3) = =IF(I2="A",1, IF(I2="B",2, IF(I2="C",3, 0))) I have started with this SQL query SELECT id, type, charSq, substr(charSq,-1,1) AS TypedChar, xCoordinate, yCoordinate, angle, distance, timestamp, speed FROM table 1 WHERE 1

Need help for the rest of the parameters. Thanks.

Note – I am going to run this in phpMyAdmin SQL