Skip to content
Create a gist now

Instantly share code, notes, and snippets.

Embed URL


Subversion checkout URL

You can clone with
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
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 {
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.