Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Estimate the minimum string length to produce a set of a given size with a minimum pairwise Hamming distance
# Use the Gilbert-Varshamov bound to estimate the minimum string length (n) that
# is required to construct a set of size x of sequences using an alphabet of size q
# with minimum Hamming distance d between any two strings in the set.
# See http://mathoverflow.net/questions/104309/how-to-find-the-minimum-string-length-to-produce-a-set-of-a-given-size-with-a-min
estimate.min.string.length <- function(x, q, d) {
if (q < 2) stop("q must be >= 2")
if (d < 1) stop("d must be >= 1")
A <- 0
# I am fairly certain by cannot prove that this is the minimum bound on n
n <- max(1, floor(log(x, q)))
while (TRUE) {
A <- gilbert.varshamov(n, q, d)
if (A < x) {
n <- n + 1
}
else {
return(n)
}
}
}
gilbert.varshamov <- function(n, q, d) {
denom <- 0
for (j in 0:(d-1)) {
denom <- denom + (choose(n, j) * ((q - 1)^j))
}
(q^n) / denom
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.