>Hi Nadya,
>
>
>>If I'm not mistaken, I heard that from my teacher of C++ course. There was one exercise to code recoursive procedure into non-recoursive. It was about 5 years ago...
>
>If you can get some examples it would be nice. I´d like to investigate those algorithms.
>Meanwhile I challenge anyone to rewrite my example in a way that is faster and non recursive.
>
>Walter,
Walter,
I have tested a couple of cases (inspiron notebook 2.2 GHz, 1024 Mb ram)
(1) Walter's best case (Test_1() below)
Given an array of 20 succeeding numbers, find the sum of all. This will in both algorithms traverse the whole search space.
Yours is indeed faster (13 secs vs 22 secs)
(2) Walter's worst case (test_2() below)
An array of 20 numbers and the target is the sum of the last two numbers
Yours takes 10.5 secs whereas mine returns in no time.
Reason: The algorithm I provided is designed to find a match where the emphasis is on providing a solution fast.
I have a customer who has a ledger account with over 15000 transactions. Any amount booked (say 100 ) must be matched eventually with -100, or any combination that results in -100( eg 250, -50, -200, -30, -70). In these circumstances I am interested in a fast solution.
If you look at both algorithms, you'll see that yours is a blind depth first search whereas mine is a blind breadth first search. Hence the difference.
I am just looking for the obvious, ie if I need to find 100, do I have 100, if not do I have two numbers that make up 100, if not do I have 3 numbers that make up 100, ...
(3) Yours is limited to 128 levels deep. Given the circumstances under (2) I am stuck
So I think this is about using the right tool for the job. You need a hammer whereas I need a saw. Difficult to compare the two tools
ps: I have modified your function a bit (you won't mind, will you). I have added the array and the number to find to the parameters
function do_it()
=test_1()
=test_2()
endfunc
function test_1()
local i, InputArray[20, 1], OutputArray[1], n, j, k, x, SolutionArray[1], Cycles, Combinations
local TimeStart, TimeEnd
for i = 1 to alen(InputArray,1)
InputArray[ i , 1] = i
endfor
InputArray[alen(InputArray,1)-1, 1] = 1000000
InputArray[alen(InputArray,1), 1] = InputArray[alen(InputArray,1)-1, 1] + 1
local NumberToFind
NumberToFind = 0
for i = 1 to alen(InputArray,1)
NumberToFind = NumberToFind + InputArray[i, 1]
endfor
?'-----------Best case'
TimeStart = seconds()
?CheckForSumIsResult(@InputArray, alen(InputArray,1), NumberToFind , 0,0,"")
TimeEnd = seconds() - TimeStart
?'CheckForSumIsResult', NumberToFind, ttoc( { 00:00 } + TimeEnd , 2), TimeEnd
TimeStart = seconds()
n = MatchNumbers(NumberToFind, @InputArray, 0, FALSE, @OutputArray, @Cycles, @Combinations)
TimeEnd = seconds() - TimeStart
?'MatchNumbers', NumberToFind, ttoc( { 00:00 } + TimeEnd , 2), TimeEnd
for i = 1 to n
?'---------'
x = strtran(OutputArray[ i, 2], ',', chr(0x0a) + chr(0x0d))
=alines(SolutionArray, x)
for j = 1 to OutputArray[ i, 1]
?? InputArray[val(SolutionArray[j]), 1]
endfor
endfor
?'Solutions:', n, 'Tested', Cycles, '/', Combinations
endfunc
function test_2()
local i, InputArray[20, 1], OutputArray[1], n, j, k, x, SolutionArray[1], Cycles, Combinations
local TimeStart, TimeEnd
for i = 1 to alen(InputArray,1)
InputArray[ i , 1] = i
endfor
InputArray[alen(InputArray,1)-1, 1] = 1000000
InputArray[alen(InputArray,1), 1] = InputArray[alen(InputArray,1)-1, 1] + 1
local NumberToFind
NumberToFind = InputArray[alen(InputArray,1), 1]+InputArray[alen(InputArray,1)-1, 1]
?'------------------Worst case'
TimeStart = seconds()
?CheckForSumIsResult(@InputArray, alen(InputArray,1), NumberToFind , 0,0,"")
TimeEnd = seconds() - TimeStart
?'CheckForSumIsResult', NumberToFind, ttoc( { 00:00 } + TimeEnd , 2), TimeEnd
TimeStart = seconds()
n = MatchNumbers(NumberToFind, @InputArray, 0, FALSE, @OutputArray, @Cycles, @Combinations)
TimeEnd = seconds() - TimeStart
?'MatchNumbers', NumberToFind, ttoc( { 00:00 } + TimeEnd , 2), TimeEnd
for i = 1 to n
?'---------'
x = strtran(OutputArray[ i, 2], ',', chr(0x0a) + chr(0x0d))
=alines(SolutionArray, x)
for j = 1 to OutputArray[ i, 1]
?? InputArray[val(SolutionArray[j]), 1]
endfor
endfor
?'Solutions:', n, 'Tested', Cycles, '/', Combinations
endfunc
Function MatchNumbers(SumToFind, InputArray, MaxDepth, MatchAll, OutputArray, Cycles, Combinations)
local Depth
Depth = alen(InputArray, 1)
do case
case empty(MaxDepth)
MaxDepth = Depth
otherwise
MaxDepth = min(MaxDepth, Depth)
endcase
local Done
Done = FALSE
local i[MaxDepth], j, k, CurrentDepth, PreviousSum[MaxDepth]
PreviousSum[1] = 0
local nSolutions, CurrentSum
nSolutions = 0
Cycles = 0
Combinations = 0
for j = 1 to MaxDepth
Combinations = Combinations + comb(Depth, j)
endfor
Local SumToFindPositive
SumToFindPositive = (SumToFind >= 0)
=iif(SumToFindPositive, asort(InputArray), asort(InputArray, 1, -1, 1))
for j = 1 to MaxDepth
do case
case Done
exit
otherwise
CurrentDepth = 1
i[CurrentDepth] = 0
do while !Done and ( CurrentDepth > 0 )
do case
case (i[CurrentDepth] < Depth + CurrentDepth - j)
i[CurrentDepth] = i[CurrentDepth] + 1
do case
case CurrentDepth = 1
CurrentSum = InputArray[ i[1], 1]
otherwise
PreviousSum[CurrentDepth] = PreviousSum[CurrentDepth-1] + InputArray[ i[CurrentDepth -1],1 ]
CurrentSum = PreviousSum[CurrentDepth] + InputArray[ i[CurrentDepth], 1]
endcase
do case
case iif(SumToFindPositive, CurrentSum > SumToFind, CurrentSum < SumToFind)
CurrentDepth = CurrentDepth - 1
case (CurrentDepth < j)
CurrentDepth = CurrentDepth + 1
i[CurrentDepth] = i[CurrentDepth-1]
case CurrentSum = SumToFind
nSolutions = nSolutions + 1
dime OutputArray[ nSolutions , 2]
OutputArray[ nSolutions, 1] = j
OutputArray[ nSolutions, 2] = transform(i[1])
for k = 2 to j
OutputArray[ nSolutions, 2] = OutputArray[ nSolutions, 2] + ',' + transform(i[k])
endfor
Done = !MatchAll
Cycles = Cycles + 1
otherwise
Cycles = Cycles + 1
endcase
otherwise
CurrentDepth = CurrentDepth - 1
endcase
enddo
endcase
endfor
return nSolutions
endfunc
function comb(n,p)
local r, i
r = n-p+1
for i = r+1 to n
r = r * i
endfor
for i = 2 to p
r = r / i
endfor
return r
endfunc
FUNCTION CheckForSumIsResult(aNumbers, nNumbers, nResultNumber, nTotal, nIndex, cCalc)
LOCAL nT
FOR nT = nIndex+1 TO nNumbers
DO CASE
CASE nTotal+aNumbers(nT,1) < nResultNumber
=CheckForSumIsResult(@aNumbers, nNumbers, nResultNumber, nTotal+aNumbers(nT,1), nT, cCalc+"+"+ALLTRIM(STR(aNumbers[NT,1],10,2)))
CASE nTotal+aNumbers(nT,1) = nResultNumber
? SUBSTR(cCalc+"+"+ALLTRIM(STR(aNumbers[nT,1],10,2)),2)
OTHERWISE
EXIT
ENDCASE
ENDFOR
RETURN
Gregory
