Hi all, I've got a very long numeric string. I want to find the lowest number that isn't in that string. E.G String = 123456 Therefore 7 is the lowest number not in that string E.G.2 String = 1234567891011 Therefore 13 is the lowest number not in that string. Any thoughts? p.s. I'm an R noob. -- View this message in context: http://r.789695.n4.nabble.com/Lowest-number-in-a-numeric-string-tp4633340.html Sent from the R help mailing list archive at Nabble.com.
On 06/14/2012 06:08 PM, mogwai84 wrote:> Hi all, > > I've got a very long numeric string. I want to find the lowest number that > isn't in that string. > > E.G > > String = 123456 > Therefore 7 is the lowest number not in that string > > E.G.2 > > String = 1234567891011 > Therefore 13 is the lowest number not in that string. > > Any thoughts? p.s. I'm an R noob. >Hi mogwai84, Your second example is inconsistent with the first. If the answer is not 12, then you must be counting the first two digits as a pair. However, that can't be right, because there are several other pairs that are much larger than 13. Are you making the assumption that all strings of digits contain monotonically increasing integers? Without a better specification of the problem, one can only guess at a solution. Jim
On Thu, Jun 14, 2012 at 01:08:53AM -0700, mogwai84 wrote:> Hi all, > > I've got a very long numeric string. I want to find the lowest number that > isn't in that string. > > E.G > > String = 123456 > Therefore 7 is the lowest number not in that string > > E.G.2 > > String = 1234567891011 > Therefore 13 is the lowest number not in that string.Hi. Try the following. s <- "1234567891011" n <- nchar(s) x <- rep(NA, times=choose(n+1, 2)) k <- 0 for (i in 1:n) { for (j in i:n) { k <- k + 1 x[k] <- as.numeric(substr(s, i, j)) } } for (i in 1:1000) { if (! i %in% x) break } print(i) [1] 13 For a longer string, we may use the fact that the number of the numbers included in the string is at most choose(n+1, 2). This implies that the lowest missing number is at most choose(n+1, 2) + 1. Due to this, we can consider only sequencies of digits of length at most ceiling(log10(choose(n+1, 2) + 1)). Hope this helps. Petr Savicky.
On Thu, Jun 14, 2012 at 01:08:53AM -0700, mogwai84 wrote:> Hi all, > > I've got a very long numeric string. I want to find the lowest number that > isn't in that string. > > E.G > > String = 123456 > Therefore 7 is the lowest number not in that string > > E.G.2 > > String = 1234567891011 > Therefore 13 is the lowest number not in that string.Hi. If the string is very long, like the first 1000 digits of pi, then try the following, which uses a better bound on the necessary number of digits than what i sent in a previous email. String <- paste(1:350, collapse="") s <- rev(as.numeric(strsplit(String, "")[[1]])) n <- length(s) for (dig in 1:9) { if (n*dig < (10^dig - 1)) break } x <- NULL for (d in 1:dig) { x <- c(x, embed(s, d) %*% 10^((d-1):0)) } x <- unique(x) for (i in 1:(10^dig - 1)) { if (! i %in% x) { print(i) break } } [1] 355 The result seems to be correct. The numbers 351, 352, 353, 354 do occur in the sequence. 351 is in "135 136", 352 in "235 236", 353 in "335 336", 354 in "53 54". Hope this helps. Petr Savicky.