find missing number function 2

[mat41]

Function findMissing(str, delim)
findMissing = ""
ar = Split(str, delim)
ar = sortIt(ar)
For i = 0 To UBound(ar) - 1
If CLng(ar(i)) + 1 <> CLng(ar(i + 1)) Then
'' we found missing number(s)
For j = 1 To (CLng(ar(i + 1)) - CLng(ar(i))) - 1
findMissing = findMissing & CStr(CLng(ar(i)) + j) & ","
Next
End If
Next
End Function

Function sortIt(ar)
For j = 0 To UBound(ar)
For i = 0 To UBound(ar) - 1
If CLng(ar(i)) > CLng(ar(i + 1)) Then
tmp = ar(i)
ar(i) = ar(i + 1)
ar(i + 1) = tmp
Exit For
End If
Next
Next
sortIt = ar
End Function

The function(s) above have been working well up until the end of last year. This week its come to my attention that:

> If the string is reasonably sequential it does what its supposed to do - find the missing numbers.
> If not it fails in a way which I am having trouble understanding. Below is an example of a string which fails:

1,2,3,4,5,6,7,8,10,11,12,13,16,17,18,19,20,21,22,25,26,27,28,29,31,32,33,35,37,38,36,30,9,39,40,42,43,44,45,24

The missing numbers in this string are 14,15,23,34 and 41. If I manually order the string sequentialy it works fine however if passed to the function in the order above the result of missing numbers is:

14,15,23,24,34,25,26,27,28,29,30,31,32,33,34,35,36,37,41

I have been looking at it for to long today. I can not work out why it says 14 is the first missing number when sequentialy 9 is. Would anybody have the time to look over it and advise me on the following:

> Are my functions a bit rough?
> If not can anyone see a mistake I have made or point out the logic why it fails in the manor it does?
> Would creating a function that orders the string sequentialy before I pass it into the above functions be prudent?

This one has be backed in a corner TYIA for any assistance

 

[markdmac]

What is the application that you are using this in?

I hope you find this post helpful.

Regards,

Mark

Check out my scripting solutions at

http://www.thespidersparlor.com/vbscript

 

[mat41]

Good day. I am using it in a classic ASP page. Its objective is to identify the missing numbers. I will check your like out, thank you. Here is an update including a cut n paste version of how I am using it

I have now discovered if i remove the last integer value (24) from the comer delimited string above it works as it should. mmmm, very strange. Is my function(s) a bit tired and therefore lack scalability? The problem doesnt seem to be because the string is not ordered sequentialy however if they are placed this way it works, mmmmm...

To see this, if one has the time, run the following code. The temporaraly hard coded 'finalString' value works with the 24 removed from the end. After you run the code comment out the 'finalString' value being used and un comment the one above, this is the problematic string:

NOTE: the output has /06 appended to the end. The numbers being run through the function are what preceeds the forward slash.

<%
Function findMissing(str, delim)
'' first split the string to get an array
'' 2nd sort the array
'' 3rd, look for the missing numbers in sequence, using mat41s method
findMissing = ""
ar = Split(str, delim)
ar = sortIt(ar)
For i = 0 To UBound(ar) - 1
If CLng(ar(i)) + 1 <> CLng(ar(i + 1)) Then
'' we found missing number(s)
For j = 1 To (CLng(ar(i + 1)) - CLng(ar(i))) - 1
findMissing = findMissing & CStr(CLng(ar(i)) + j) & ","
Next
End If
Next
End Function

Function sortIt(ar)
For j = 0 To UBound(ar)
For i = 0 To UBound(ar) - 1
If CLng(ar(i)) > CLng(ar(i + 1)) Then
tmp = ar(i)
ar(i) = ar(i + 1)
ar(i + 1) = tmp
Exit For
End If
Next
Next

sortIt = ar
End Function


'finalString = "1,2,3,4,5,6,7,8,10,11,12,13,16,17,18,19,20,21,22,25,26,27,28,29,31,32,33,35,37,38,36,30,9,39,40,42,43,44,45,24"
finalString = "1,2,3,4,5,6,7,8,10,11,12,13,16,17,18,19,20,21,22,25,26,27,28,29,31,32,33,35,37,38,36,30,9,39,40,42,43,44,45"
If len(finalString) > 2 Then
missingNumArray = split(findMissing(finalString, ","),",")
For numCount2 = 0 To ubound(missingNumArray)-1
response.write missingNumArray(numCount2) & "/0" & right(osirNum, 1) & ", "
Next
Set missingNumArray = nothing
End if
%>

Any ideas would be much appreciated TYIA

 

[mat41]

marcdmac - lots of useful scripts there I will be sure to have a look when I solve this issue...

 

[tsuji]

Though sortIt()is O(n^2) sorting routine, it sure performs reasonably well except for hugh entries. But, you have two important flaws in the construction.

[1] The permutation

> For i = 0 To UBound(ar) - 1
> If CLng(ar(i)) > CLng(ar(i + 1)) Then
> tmp = ar(i)
> ar(i) = ar(i + 1)
> ar(i + 1) = tmp
> Exit For
> End If
> Next

should be read like this.
[tt]
For i = 0 To UBound(ar)
If CLng(ar(j)) > CLng(ar(i)) Then
tmp = ar(j)
ar(j) = ar(i)
ar(i) = tmp
[red]'[/red]Exit For
End If
Next
[/tt]
See the difference?

[2] This is fundamental. Your naming of variable makes the scope terribly mixed up. It might not surface as such, but with your line
>ar = sortIt(ar)
before reassign to ar from the return array of sortIt, ar itself has already changed to the sorted array due to the scoping mixed up. If you prefer to keep the naming of ar in the sortIt function, this is the quick fix.

>Function sortIt(ar)
[tt]Function sortIt([red]byval[/red] ar)[/tt]

Better, rename the argument name from ar to something else so as not to collide with the array passing from findmissing function. It's up to you.

 

[tsuji]

Amendment

Had a to-be-edited missed out in the indexing. A retake.
[tt]
For i = [red]j[/red] To UBound(ar)
If CLng(ar(j)) > CLng(ar(i)) Then
tmp = ar(j)
ar(j) = ar(i)
ar(i) = tmp
'Exit For
End If
Next
[/tt]

 

[PHV]

And what about this ?

Function findMissing(str, delim)
findMissing = ""
ar = sortIt(Split(str, delim))
For i = 0 To UBound(ar) - 1
  If CLng(ar(i)) + 1 <> CLng(ar(i + 1)) Then
    For j = 1 To CLng(ar(i + 1)) - CLng(ar(i)) - 1
      findMissing = findMissing & (ar(i) + j) & ","
    Next
  End If
Next
End Function

Function sortIt(ar)
For j = 0 To UBound(ar) - 1
  For i = j To UBound(ar)
    If CLng(ar(j)) > CLng(ar(i)) Then
      tmp = ar(i)
      ar(i) = ar(j)
      ar(j) = tmp
    End If
  Next
Next
sortIt = ar
End Function

Hope This Helps, PH.
Want to get great answers to your Tek-Tips questions? Have a look at FAQ219-2884 or FAQ181-2886

 

[EBGreen]

An alternative method. I'm not sure how it would compare in benchmarking however:


strTest = "1,2,3,4,5,6,7,8,10,11,12,13,16,17,18,19,20,21,22,25,26,27,28,29,31,32,33,35,37,38,36,30,9,39,40,42,43,44,45,24"
WScript.Echo FindMissingNumbers(strTest)
Function FindMissingNumbers(strIn)
Dim nMin
Dim nMax
Dim arrIn
Dim nNumber
Dim strOut

arrIn = Split(strIn, ",")
strIn = "," & strIn & ","
nMin = CInt(arrIn(0))
nMax = CInt(arrIn(0))
For Each nNumber In arrIn
If CInt(nNumber) > nMax Then
WScript.Echo "New Max = " & nNumber
nMax = CInt(nNumber)
End If
If CInt(nNumber) < nMin Then
WScript.Echo "New Min = " & nNumber
nMin = CInt(nNumber)
End If
Next
WScript.Echo "Looping from " & nMin & " to " & nMax
For nNumber = nMin To nMax
If Not InStr(strIn, "," & nNumber & ",") > 0 Then
WScript.Echo "Missing " & nNumber
strOut = strOut & "," & nNumber
End If
Next
FindMissingNumbers = Mid(strOut, 2)
End Function

[red]"... isn't sanity really just a one trick pony anyway?! I mean, all you get is one trick, rational thinking, but when you are good and crazy, oooh, oooh, oooh, the sky is the limit!" - The Tick[/red]

 

[mat41]

wow what a forum, you guys are tops. I am in aussie and have just got to the office now. On the bus this came into play:

Function sortIt(ar)
For j = 0 To UBound(ar) - 1
For i = j + 1 To UBound(ar)
If ar(i) - ar(j) < 0 Then
tmp = ar(j)
ar(j) = ar(i)
ar(i) = tmp
End If
Next
Next
sortIt = ar
End Function

The sorting function was poor. Now I am spoilt for choice I will go through the posts here now. Thankyou very much