Permutations in VBA

Question

Can someone please help me with an example on this?

I'm trying to wrap my mind around how run simple permutations using a loop.

Suppose I have a variable amount of items that can be assigned True of False.

2, 3, 4, or 6 items. 

I'd like to show all the different orders the True and False can be assigned.

For 2 items:  

True, True

True, False

False, True

False, False

For 3 items: 

True, True, True

True, True, False

True, False, True

False, True, True

False, False, True

and so forth.

Whats throwing me off is how to account for the variable amount of items that the True and False could apply to. 

The example below uses ones and zeroes in place of the True and False.

Sub attempt()

Options = Array(0, 1)

Count = 1

For a = LBound(Options) To UBound(Options)

    For b = LBound(Options) To UBound(Options)

        For c = LBound(Options) To UBound(Options)

            ActiveSheet.Cells(Count, 1) = a & "_" & b & "_" & c

            Count = Count + 1

        Next c

     Next b

Next a

End Sub

How can you make the code accept a variable number of items (a,b,c,d,e...) and find different combinations of ones and zeroes for them?

Thank you

Answer 1

Sub doit()

Const nItems As Long = 3    ' up to 20 in XL2007+

Const xMax As Long = 2 ^ nItems - 1

Dim x As Long, t As Long, i As Long

Dim s As String, res(0 To xMax, 1 To 1) As String

If nItems > Log(Rows.Count) / Log(2) Then

    MsgBox "too many"

    Exit Sub

End If

Columns("a").Clear

For x = 0 To xMax

    t = x: s = ""

    For i = 1 To nItems

        s = IIf(t And 1, "True", "False") & ", " & s

        t = t \ 2

    Next i

    res(x, 1) = Left(s, Len(s) - 2)

Next x

Range("a1:a" & xMax + 1) = res

Columns("a").AutoFit

MsgBox "done"

End Sub

Caveat:  Before setting nItems very large, I suggeest that you test the behavior using increasing values for nItems.  On my laptop, the performance started to decline badly for nItems > 15, although it did work eventually.  I suspect that memory and/or cache management becomes a performance factor.

Answer 2

I printed your code out on a little piece of paper. I carried it around with me and stared at it for the better part of the weekend...

I built it in as a 'permutator' in my script and the solution works. 

I realize that there is still much potential to improve the efficiency of the solution, but I did want to see how permutations could be generated with code. 

At first glance I thought that the code was taking numbers from x to xmax and continually dividing them by 2 and assigning TRUE to those that were divisible. As I tried to follow it, I realized I was far off. 

Before I saw your last post I was trying to figure out why (1 AND 3) or (1 AND 1) gave 1 and (1 AND 2) gave 0. Then I got to the bitwise/binary concept. 

It's awesome that you can visualize this solution. Do you think it's a result of your academic background or job experience?

Would you be able to suggest some material that shows more of these kind of concepts?

Because this is not ordinary excel macro stuff. 

Thank you

Answer 3

excelKangaroo wrote:

This code is very interesting, I'll dig in to figure out how you made it do what it does. I see a couple things I'm not familiar with.  Thank you for your help!

You're welcome.  I'll try to explain.  But first let me say:  if you presented the actual problem instead of an abstraction, there might be a better implementation.  Your abstraction might not be good analogy for the actual problem.

As for my implemenation....

If you have a combination of n 0s and 1s, the combination can be represented by a binary variable consisting of n bits.  For all such n-bit combinations, the variable can have the values 0 through 2^n - 1.

For example, for 3 0s and 1s (3 bits), the variable can have the values 0 through 7 (2^3 - 1).  In binary, that is 000, 001, 010, 011, 100, 101, 110, 111.

We can extract the right-most bit with the expression t AND 1.  So that returns 1 or 0.

We can shift the variable to the right with the expression t \ 2, which is shorthand for Int(t / 2).  Note the difference between backslash and (forward) slash.

Answer 4

Believe it or not, its not for school! :)

I will use the concept to be able to populate cells in a column with True and False criteria (many different permutations of True and False across a few select cells in a column ).

After each found permutation/ input, I'll make it  call another script to spit out a result based on the the different True and False inputs. 

This code is very interesting, I'll dig in to figure out how you made it do what it does. I see a couple things I'm not familiar with.

Thank you for your help!