# Help me design a recursive function in Excel VBAAugust 1, 2024 10:52 AM   Subscribe

For kicks, I've been toying around with recursive functions in VBA, but I'm stuck. A simple model of my problem is that I have a casette, with 10 slots, each slot (numbered 1 - 10) can have a number in it from 0 - 9. I'd like find combinations where the sum of all casettes = 11. Note the checktrue function is arbitrary, I'd like to be able to swap it for other things. The current code finds one solution, which is great. Now I want to run the code in a way that finds 100 solutions but finding all possible solutions by varying the early slots, as opposed to the late slots.

When the code picks 0 for slot 1, I can't find an easy way for it go back and then pick 1 for slot 1, and after the next solution, 2 for slot 2.

I've made a pastebin as well.
Public casette As Variant
Public Solutions As Collection
Public SolSkip As Long

Sub Stp()
Set Solutions = New Collection
SolSkip = 0
ReDim casette(1 To 10)
Debug.Print
Do Until Solutions.Count > 10
ReDim casette(1 To 10)
Call Casettefiller(1)
Loop
End Sub

Function Casettefiller(Start As Variant, Optional skipnum As Long)

If Start > UBound(casette) Then
Debug.Print "No solution found"
Casettefiller = -1
Exit Function

End If

For i = 1 To 9
casette(Start) = i
Select Case CheckTrue(casette)
Case 1
Casettefiller = 1
SolSkip = SolSkip + 1
Exit Function

Case 0
Select Case Casettefiller(Start + 1)
Case 1
Casettefiller = 1
Exit Function
Case -1
End Select
Case -1
End Select
Next

End Function

Function CheckTrue(casette As Variant)

Dim i As Long
Dim cCount As Long
Dim target As Long
target = 11

cCount = 0
For i = LBound(casette, 1) To UBound(casette, 1)
cCount = casette(i) + cCount
Next

If cCount < target Then CheckTrue = 0 'there's more to go!
If cCount = target Then CheckTrue = 1 'we're there!
If cCount > target Then CheckTrue = -1 'too much!
End Function

posted by cacofonie to Computers & Internet (9 answers total) 1 user marked this as a favorite

This is the sort of thing ChatGPT can be good at. You obviously need to check bestie's work, which I can't do because I am VBA illiterate. Note it is explicitly looking for 100 solutions:

Option Explicit

Dim solutionsCount As Integer

Sub FindSolutions()
Dim slots(1 To 10) As Integer
solutionsCount = 0
FindCombinations slots, 1, 0, 11
End Sub

Sub FindCombinations(ByRef slots() As Integer, ByVal index As Integer, ByVal currentSum As Integer, ByVal targetSum As Integer)
Dim i As Integer

' Base case: all slots are filled
If index > UBound(slots) Then
If currentSum = targetSum Then
' Process or display the solution
PrintSolution slots
solutionsCount = solutionsCount + 1
If solutionsCount >= 100 Then
Exit Sub
End If
End If
Exit Sub
End If

' Try all values from 0 to 9 in the current slot
For i = 0 To 9
slots(index) = i
If currentSum + i <> FindCombinations slots, index + 1, currentSum + i, targetSum
End If
Next i
End Sub

Sub PrintSolution(ByVal slots() As Integer)
Dim i As Integer
Dim output As String
output = ""
For i = LBound(slots) To UBound(slots)
output = output & slots(i) & " "
Next i
Debug.Print output
End Sub

If you want the notes, let me know and I will pastebin it for you, but I am very curious to see if this is a functional solution!
posted by DarlingBri at 11:25 AM on August 1 [1 favorite]

What you are describing is a cartesian product which can be generated in any database with one line of SQL:

Select casettes.id, numbers.id from casettes, numbers;
posted by Lanark at 11:31 AM on August 1

This isn't a cartesian product. The cartesian product would get you all possible orderings with repetition, regardless of their sum.

If order doesn't matter, these are most of the partitions of 11, namely all partitions except 11 and 10+1.

A recursive pseudocode implementation is something like:

def partitions(n):
ans = empty list
for i from max(9, i ) to 0:
for rest in partitions(n-i):
Add (i + rest) to and
return ans
posted by hoyland at 11:50 AM on August 1

I think hoyland has the right mathematical answer, but note that Excel and VBA keep a cap on the number of loops it will evaluate.

The LAMBDA() wrapper is exempted from this restriction [1], and it may be your code stops because of the restriction.

posted by k3ninho at 12:21 PM on August 1

Response by poster: Thanks for the quick replies!

Re: ChatGPT -> I've already tried both claude and GPT and they both get stuck.

Re: partitions of 11 - I want to clarify, I'm not trying to find alternative ways to get solution of 11 -> thats just a random constraint that I invented.

My core question is I have designed this recursive function. When it finds a solution, I want it to try and find the next solution by varying the earliest possible decision point that hasn't been tried yet.

So for example, the first run with the code as I've written it is to find the solution 000000029. I want to then run the next solution i want it to try is 100000019, and then 200000009, etc.
posted by cacofonie at 12:37 PM on August 1

Best answer: It sounds like you're trying to interleave two different orderings, which is far from any standard solution to this type of problem.

If I understand correctly, right now you have a function that assigns values to your positions from left to right, backtracking when it runs out of options in one position to try the next value of the previous position. That's a standard way to recursively enumerate these sorts of combinations.

Typically, when you want multiple solutions, you just have the algorithm continue with the same ordering and the same recursion after it finds any solution. But it sounds like you want it to make a very different decision in the step after it finds each solution.

One thing that isn't clear: do you want it to skip some solutions and never find them? In your example, you've skipped 00...038, 00...047, etc. Is that a desired outcome?

Also, do you want exactly the ordering you've specified, or is the goal more to initially get diverse solutions that are more "spread out" in the space than the typical recursion will find?

If you mostly want diverse solutions, then keep your existing algorithm, but restart it from a random new "position" after each solution is found. That is, randomize the values in all positions, then start the recursion as if you just assigned a value to the final position, backtracking and enumerating from that point.

If you want exactly the ordering in your example, then you could possibly nest and interleave two recursive enumerations:
• The "inner" recursion is exactly what you have already.
• The outer recursion enumerates all combinations by assigning the rightmost values first and otherwise using the same backtracking enumeration approach. Same algorithm, different variable/position ordering. So it will generate 00...00, 10...00, 20...00, etc. in that order. Every time this recursion generates one complete assignment (i.e., every time it assigns a new value to the leftmost position): start the "inner" recursion from that assignment.
This way you start one "inner" recursion from 00...00 as you do now. Then you start another from 10...00 and find a solution from there. Then start one from 20...00. And so on. You'll get to 90...00, find one solution, then try 010...00 next.

In any case, one way to approach this is to set up your existing algorithm to let it "start" from any specified assignment to your positions, and then you can think about what "starting points" to pass to that algorithm and how to generate them separately.
posted by whatnotever at 3:52 PM on August 1

Response by poster: Thanks whatnotever. You've figured me out! The actual use purpose of this is a recursive algorithm I've built to find a schedule. But I want it to find LOTS of schedules - and really different ones.

So I figured, if I could find a way to have it go back to the first fork in the road and turn right instead of left, that would give me the most different schedule. I thought it would be easy to backjump to that first fork, but it seems to be most challenging.

Reading through your response, I guess I should go the randomizing route. I just thought going from the FIRST fork would give me the most diverse choices.

Your idea of TWO recursions, the first one finding the position, the second one filling the casette is BRILLIANT, but I wonder if it would work with my complicated use case. I will digest this and see. Thanks!
posted by cacofonie at 6:20 PM on August 1

Basically all programming systems have some limit on recursion depth - the number of times a function can call itself. Microsoft discusses this for VBA here.
posted by SemiSalt at 4:42 AM on August 2

If you want to generate schedules that are not similar or "clumped together," then the idea of changing a value on the "left" of the assignment after finding a solution won't necessarily do that super well. E.g., in the example scenario, it won't find any solutions with non-zero values in the "middle" of the set of variables -- at least not until much later in the enumeration.

Note that random starting points might give you trouble with efficiency, though. Again, using the example scenario, if a random starting point is 8523729412, then with the standard recursive ordering, no solutions at all will be found until it eventually backtracks enough to change the first digit and get to 9000000000, soon reaching 900...02. (Nothing starting with 85, 86, 87, 88, or 89 will be a valid solution.) Going through the roughly 500 million assignments before that may take a while. The impact of this basically depends on how common valid solutions are in the total solution space and how large the solution space is relative to how quickly your code can enumerate it.

So if that is an issue, another algorithmic approach to consider is local search. Again, it will start from a randomized assignment. But if that assignment is not a valid solution, the idea is to generate a small set of assignments "nearby" the current one (e.g., any assignment made by adding or subtracting 1 to a single variable), measure how "close" each of those is to a solution, take the closest one, and repeat the process. This requires that you are able to calculate some metric for the distance from a valid solution; in the example scenario that could just be the difference between the sum of the values in the assignment and 11. More generally it might be a count of how many of the constraints that define "valid" are violated. And again, how successful and efficient this is depends a lot on the shape of the solution space, how common valid solutions are, etc. (Unlike complete enumeration, local search can fail to find anything by getting "stuck" in a space with no "moves" that get closer to a solution. In that case you can always restart with a new random assignment, though.)
posted by whatnotever at 2:13 PM on August 2

« Older What's up with the Venezuelan elections?   |   Recommend a resume writer for a hard-to-categorize... Newer »

You are not logged in, either login or create an account to post comments