Instantly share code, notes, and snippets.

jdidion/gist:84bae05a5c3344710fb5Secret Created Aug 9, 2012

What would you like to do?
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 }