Estimate the minimum string length to produce a set of a given size with a minimum pairwise Hamming distance

gistfile1.r

# 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
}