>Hello all,
>
>For a bank reconciliation program, I am trying to simulate a situation which mimics lottery possibilities
>
>For example I have a series of numbers 1, 2, 3 and 4.
>I need to find all the possible combinations of those numbers (in any order), which are:
>1+2, 1+3, 1+4, 1+2+3, 1+2+4, 1+3+4,1+2+3+4, 2+3, 2+4, 2+3+4, 3+4.
>
>I need to write code for that and could not find any solution so far.
>Could someone enlighten me with an idea.
>
>Thanks in advance
>
>Jonathan Feldman

Jonathan,

Here's an algorithm you may want to consider

You pass
- a number to find which is the sum of any combination
- a two dimensional input array. The first column contains a number. The other columns may contain related information to the first column such as a transaction number
- max depth, ie the max # of items that can contribute to the reconstruction of the number to find. Zero for all
- MatchAll: TRUE to find all possibilites, FALSE to exit on the first hit
- an Output array (see format in sample)
- Cycles (optional): # cycles tested
- Combinations(optional): the max # of combinations that can be tested

It returns the number of solutions found

It does a breadth first search (all combinations of 1, all combinations of 2, all combinations of 3, ..., up to max depth) and prunes nodes that are not promising

It sorts your input array in either ascending or descending order depending on the number you are trying to find

I do not use recursion as this will only slow down the process

*---------------------------------------------------------------------------
function do_it()

	local i, InputArray[20, 2], OutputArray[1], n, j, x, SolutionArray[1], Cycles, Combinations
	
	
	dime InputArray[10, 2]
	for i = 1 to alen(InputArray,1)
		InputArray[ i , 1] =  i * iif(empty(mod(i,2)), -1, 1) *(-1)
	endfor
	
	
	n = MatchNumbers(0, @InputArray, 0, TRUE, @OutputArray, @Cycles, @Combinations)
	
	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)
	
	&& MaxDepth tells us the max # of items contributing to the sum to find
	&&		zero = unlimited
	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)
						&& discard node
						CurrentDepth = CurrentDepth - 1
						
					case (CurrentDepth < j)	&& not at full MaxDepth
						CurrentDepth = CurrentDepth + 1
						i[CurrentDepth] = i[CurrentDepth-1]
						
					case CurrentSum = SumToFind	&& bingo
						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
	for i = 1 to p-1
		r = r * (n-i)
	endfor
	for i = 0 to p-1
		r = r / (p-i)
	endfor
	return r
endfunc
*---------------------------------------------------------------------------