Combination algorithm for indefinite string arrays

[paragpdoke]

Hello All.
I'm looking for some algorithm to build a combination of strings from multiple arrays. Let me explain in detail.

- I'm working on VBA (excel). I have functions that accept one string and return a collection. These get listed in columns in excel (one column per call to the function).
- This results into arrays of strings in different columns. Unfortunately, the number of strings in an array is unknown at design time (these get retrieved from another sheet by other functions) and so are the number of columns / arrays (these depend on user interaction) and both are out of my control :-(.
- What I am supposed to do is build up a combination of all possible string values from each of these columns. I've been looking for something like an algorithm / flowchart for a headstart.

Any help towards this objective is welcome. Existing links to articles will also be fine.
Thanks in advance,
Parag

[paragpdoke]

I showed the problem description to a colleague. She said it wasn't very clear. So I thought of adding something more.
I'm not trying to look for how to populate those arrays. I want to start after they have been populated.

Arr1    Arr2    Arr3    ...  ArrN
S11     S21     S31     ...  SN1
S12     S22     S32     ...  SN2
S13     S23     S33     ...  SN3
.       .       .       .    .
.       .       .       .    .
.       .       .       .    .
S1A     S2B     S3C     ...  SNX
 

[kadghar]

Hello All.
I'm looking for some algorithm to build a combination of strings from multiple arrays. Let me explain in detail.

- I'm working on VBA (excel). I have functions that accept one string and return a collection. These get listed in columns in excel (one column per call to the function).
- This results into arrays of strings in different columns. Unfortunately, the number of strings in an array is unknown at design time (these get retrieved from another sheet by other functions) and so are the number of columns / arrays (these depend on user interaction) and both are out of my control :-(.
- What I am supposed to do is build up a combination of all possible string values from each of these columns. I've been looking for something like an algorithm / flowchart for a headstart.

Any help towards this objective is welcome. Existing links to articles will also be fine.
Thanks in advance,
Parag

If i understood well, what you have is a string, lets say "Hello", and you get an array from it, lets say Arr1, where
Arr1(0) = H
Arr1(1) = e
Arr1(2) = l
Arr1(3) = l
Arr1(4) = o
and you want the list of all the possible combinations, like
H, e, l, o, He, Hl, Ho, el, eo, ll, lo Hel, Heo, Hll, Hlo, ell, and so...

Well, if im right, what you want is not a simple task. Check this thread, with a similar problem we've been discussing recently. It might be of help.
Anyway, if I didnt understand you, or the algorithm is not clear (because it is not), or you still have doubts, we'll be glad to help.

[Killer42]

... Anyway, if I didnt understand you, or the algorithm is not clear (because it is not), or you still have doubts, we'll be glad to help.

Hahaha... yeah, when you have a complex situation like this it can be very difficult to describe in writing and get others to understand it. Let's hope we're getting somewhere near the true situation. Remember, the more clearly you can describe it to us (and the more examples we see of what is expected to happen) the more we'll be able to help.

The way I see it, you have an unknown number of columns, each containing an unknown number of entries (rows). You need to extract all the possible combinations. so in your quoted example, the combinations would be

S11S21S31...SN1
S11S21S31...SN2
S11S21S31...SN3
.
.
.

If this is anywhere close to what you're after, it shouldn't be too tough. From what you've said, these may be already in arrays. My terminology will probably get somewhat jumbled here, but I'll refer to columns and rows for (hopefully) simplicity. We can adjust things later as required. How about something along the lines of...

Determine the number of columns, c.
Define a numeric array ColLength with c entries.
Define an identical numeric array ColPos with c entries.
Populate ColLength array with the number of entries in each column.
Set all the elements in the ColPos to 1.
In an "infinite" loop...
  Concatenate the cells pointed to by all the entries in ColPos array.
  Increment entry c in your ColPos array.
  If ColPos(c) > ColLength(c) Then
    Set ColPos(c) back to 1
    Increment the next ColPos entry to the left
  End If
  Continue this sequence all the way to the left...
  If all ColPos entries have reached their corresponding ColLength value then
    Exit Loop (we've done them all)
  End If
End Loop
 

Does this make sense to anyone? It was straight off the top of my head.

What I'm trying to do here is actually fairly simple, just producing an array of numbers pointing to the positions to be concatenated. So the array would point to...

1,1,1...,1
1,1,1...,2
1,1,1...,3

and so on.

[paragpdoke]

Hello kadghar.
No...I was looking for what Killer42 explained.

Killer42,
Thank you for this explanation. I was able to get something to work on these lines. It is not working 100% for me (but that's not a problem with the method, it is a problem with my VB code). Thank you once again.

Regards,
Parag

[Killer42]

Glad I could help. :)

Accurately defining the problem (and the process) is often the hardest part of programming. If you can work out in enough detail what you want the program to do, it almost writes itself. (After all, that's all a program really is - a description of the process in a form simple (and consistent) enough for a compiler to understand).

How about posting what you end up with, for future reference?

[paragpdoke]

Glad I could help. :)

Accurately defining the problem (and the process) is often the hardest part of programming. If you can work out in enough detail what you want the program to do, it almost writes itself. (After all, that's all a program really is - a description of the process in a form simple (and consistent) enough for a compiler to understand).

How about posting what you end up with, for future reference?

Yes. I was planning to post it....but was afraid my VB code is far too rudimentary to be posted on a public forum. Instead of the iterator method as you explained, someone told me to try a recursive approach. His approach / code is "postable" and mine is not. So for future reference, let me post this one instead [not 100% right...but close.]

Option Explicit
Private Sub Command_Click()
 
Dim Word1 As New Collection
Word1.Add "Word11"
Word1.Add "Word12"
Word1.Add "Word13"
Word1.Add "Word14"
 
Dim Word2 As New Collection
Word2.Add "Word21"
Word2.Add "Word22"
Word2.Add "Word23"
Word2.Add "Word24"
 
Dim Word3 As New Collection
Word3.Add "Word31"
Word3.Add "Word32"
Word3.Add "Word33"
Word3.Add "Word34"
 
Dim WordsCol As New Collection
WordsCol.Add Word1
WordsCol.Add Word2
WordsCol.Add Word3
 
 
Dim IteratorString As Variant
For Each IteratorString In GenerateCombinations(vbNullString, WordsCol)
    Debug.Print IteratorString
Next IteratorString
 
End Sub
 
Function GenerateCombinations(CurrentString As String, NextCollection As Collection) As Collection
    Dim IteratorString As Variant
    Dim ReturnCollection As New Collection
    Dim CurrentCollection As Collection
    Set CurrentCollection = NextCollection.Item(1)
    If NextCollection.Count > 1 Then
        NextCollection.Remove (1)
        For Each IteratorString In CurrentCollection
            Dim NextIterator As Variant
            For Each NextIterator In GenerateCombinations(CurrentString & "-" & CStr(IteratorString), NextCollection)
                ReturnCollection.Add NextIterator
            Next NextIterator
        Next IteratorString
        NextCollection.Add CurrentCollection, , 1
    Else
        For Each IteratorString In CurrentCollection
            ReturnCollection.Add CurrentString & "-" & CStr(IteratorString)
        Next IteratorString
    End If
    Set GenerateCombinations = ReturnCollection
    Set ReturnCollection = Nothing
    Set CurrentCollection = Nothing
End Function
 
 

The output:

-Word11-Word21-Word31
-Word11-Word21-Word32
-Word11-Word21-Word33
-Word11-Word21-Word34
-Word11-Word22-Word31
-Word11-Word22-Word32
-Word11-Word22-Word33
-Word11-Word22-Word34
-Word11-Word23-Word31
-Word11-Word23-Word32
-Word11-Word23-Word33
-Word11-Word23-Word34
-Word11-Word24-Word31
-Word11-Word24-Word32
-Word11-Word24-Word33
-Word11-Word24-Word34
-Word12-Word21-Word31
-Word12-Word21-Word32
-Word12-Word21-Word33
-Word12-Word21-Word34
-Word12-Word22-Word31
-Word12-Word22-Word32
-Word12-Word22-Word33
-Word12-Word22-Word34
-Word12-Word23-Word31
-Word12-Word23-Word32
-Word12-Word23-Word33
-Word12-Word23-Word34
-Word12-Word24-Word31
-Word12-Word24-Word32
-Word12-Word24-Word33
-Word12-Word24-Word34
-Word13-Word21-Word31
-Word13-Word21-Word32
-Word13-Word21-Word33
-Word13-Word21-Word34
-Word13-Word22-Word31
-Word13-Word22-Word32
-Word13-Word22-Word33
-Word13-Word22-Word34
-Word13-Word23-Word31
-Word13-Word23-Word32
-Word13-Word23-Word33
-Word13-Word23-Word34
-Word13-Word24-Word31
-Word13-Word24-Word32
-Word13-Word24-Word33
-Word13-Word24-Word34
-Word14-Word21-Word31
-Word14-Word21-Word32
-Word14-Word21-Word33
-Word14-Word21-Word34
-Word14-Word22-Word31
-Word14-Word22-Word32
-Word14-Word22-Word33
-Word14-Word22-Word34
-Word14-Word23-Word31
-Word14-Word23-Word32
-Word14-Word23-Word33
-Word14-Word23-Word34
-Word14-Word24-Word31
-Word14-Word24-Word32
-Word14-Word24-Word33
-Word14-Word24-Word34
 
 

[Killer42]

Yes. I was planning to post it....but was afraid my VB code is far too rudimentary to be posted on a public forum.

I have that problem all the time. :)

Thanks for posting the code, anyway. And I'm sure we're all glad to see you got it working.

[frajag]

Hi,

I am quite new to VBA (sort of) and I would like to use this code in an excel macro so that the output would be on a new tab.

Can you please help?

Thanks

Francois

[paragpdoke]

Hello Francois.
I believe the code is okay to be used within a VBA macro.

Regards,
Parag Doke