By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,509 Members | 1,301 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,509 IT Pros & Developers. It's quick & easy.

Combination algorithm for indefinite string arrays

P: 62
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
Mar 12 '08 #1
Share this Question
Share on Google+
9 Replies


P: 62
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.
Expand|Select|Wrap|Line Numbers
  1. Arr1    Arr2    Arr3    ...  ArrN
  2. S11     S21     S31     ...  SN1
  3. S12     S22     S32     ...  SN2
  4. S13     S23     S33     ...  SN3
  5. .       .       .       .    .
  6. .       .       .       .    .
  7. .       .       .       .    .
  8. S1A     S2B     S3C     ...  SNX
  9.  
Mar 12 '08 #2

kadghar
Expert 100+
P: 1,295
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.
Mar 12 '08 #3

Expert 5K+
P: 8,434
... 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...
Expand|Select|Wrap|Line Numbers
  1. Determine the number of columns, c.
  2. Define a numeric array ColLength with c entries.
  3. Define an identical numeric array ColPos with c entries.
  4. Populate ColLength array with the number of entries in each column.
  5. Set all the elements in the ColPos to 1.
  6. In an "infinite" loop...
  7.   Concatenate the cells pointed to by all the entries in ColPos array.
  8.   Increment entry c in your ColPos array.
  9.   If ColPos(c) > ColLength(c) Then
  10.     Set ColPos(c) back to 1
  11.     Increment the next ColPos entry to the left
  12.   End If
  13.   Continue this sequence all the way to the left...
  14.   If all ColPos entries have reached their corresponding ColLength value then
  15.     Exit Loop (we've done them all)
  16.   End If
  17. End Loop
  18.  
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.
Mar 14 '08 #4

P: 62
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
Mar 15 '08 #5

Expert 5K+
P: 8,434
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?
Mar 17 '08 #6

P: 62
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.]
Expand|Select|Wrap|Line Numbers
  1. Option Explicit
  2. Private Sub Command_Click()
  3.  
  4. Dim Word1 As New Collection
  5. Word1.Add "Word11"
  6. Word1.Add "Word12"
  7. Word1.Add "Word13"
  8. Word1.Add "Word14"
  9.  
  10. Dim Word2 As New Collection
  11. Word2.Add "Word21"
  12. Word2.Add "Word22"
  13. Word2.Add "Word23"
  14. Word2.Add "Word24"
  15.  
  16. Dim Word3 As New Collection
  17. Word3.Add "Word31"
  18. Word3.Add "Word32"
  19. Word3.Add "Word33"
  20. Word3.Add "Word34"
  21.  
  22. Dim WordsCol As New Collection
  23. WordsCol.Add Word1
  24. WordsCol.Add Word2
  25. WordsCol.Add Word3
  26.  
  27.  
  28. Dim IteratorString As Variant
  29. For Each IteratorString In GenerateCombinations(vbNullString, WordsCol)
  30.     Debug.Print IteratorString
  31. Next IteratorString
  32.  
  33. End Sub
  34.  
  35. Function GenerateCombinations(CurrentString As String, NextCollection As Collection) As Collection
  36.     Dim IteratorString As Variant
  37.     Dim ReturnCollection As New Collection
  38.     Dim CurrentCollection As Collection
  39.     Set CurrentCollection = NextCollection.Item(1)
  40.     If NextCollection.Count > 1 Then
  41.         NextCollection.Remove (1)
  42.         For Each IteratorString In CurrentCollection
  43.             Dim NextIterator As Variant
  44.             For Each NextIterator In GenerateCombinations(CurrentString & "-" & CStr(IteratorString), NextCollection)
  45.                 ReturnCollection.Add NextIterator
  46.             Next NextIterator
  47.         Next IteratorString
  48.         NextCollection.Add CurrentCollection, , 1
  49.     Else
  50.         For Each IteratorString In CurrentCollection
  51.             ReturnCollection.Add CurrentString & "-" & CStr(IteratorString)
  52.         Next IteratorString
  53.     End If
  54.     Set GenerateCombinations = ReturnCollection
  55.     Set ReturnCollection = Nothing
  56.     Set CurrentCollection = Nothing
  57. End Function
  58.  
  59.  
The output:
Expand|Select|Wrap|Line Numbers
  1. -Word11-Word21-Word31
  2. -Word11-Word21-Word32
  3. -Word11-Word21-Word33
  4. -Word11-Word21-Word34
  5. -Word11-Word22-Word31
  6. -Word11-Word22-Word32
  7. -Word11-Word22-Word33
  8. -Word11-Word22-Word34
  9. -Word11-Word23-Word31
  10. -Word11-Word23-Word32
  11. -Word11-Word23-Word33
  12. -Word11-Word23-Word34
  13. -Word11-Word24-Word31
  14. -Word11-Word24-Word32
  15. -Word11-Word24-Word33
  16. -Word11-Word24-Word34
  17. -Word12-Word21-Word31
  18. -Word12-Word21-Word32
  19. -Word12-Word21-Word33
  20. -Word12-Word21-Word34
  21. -Word12-Word22-Word31
  22. -Word12-Word22-Word32
  23. -Word12-Word22-Word33
  24. -Word12-Word22-Word34
  25. -Word12-Word23-Word31
  26. -Word12-Word23-Word32
  27. -Word12-Word23-Word33
  28. -Word12-Word23-Word34
  29. -Word12-Word24-Word31
  30. -Word12-Word24-Word32
  31. -Word12-Word24-Word33
  32. -Word12-Word24-Word34
  33. -Word13-Word21-Word31
  34. -Word13-Word21-Word32
  35. -Word13-Word21-Word33
  36. -Word13-Word21-Word34
  37. -Word13-Word22-Word31
  38. -Word13-Word22-Word32
  39. -Word13-Word22-Word33
  40. -Word13-Word22-Word34
  41. -Word13-Word23-Word31
  42. -Word13-Word23-Word32
  43. -Word13-Word23-Word33
  44. -Word13-Word23-Word34
  45. -Word13-Word24-Word31
  46. -Word13-Word24-Word32
  47. -Word13-Word24-Word33
  48. -Word13-Word24-Word34
  49. -Word14-Word21-Word31
  50. -Word14-Word21-Word32
  51. -Word14-Word21-Word33
  52. -Word14-Word21-Word34
  53. -Word14-Word22-Word31
  54. -Word14-Word22-Word32
  55. -Word14-Word22-Word33
  56. -Word14-Word22-Word34
  57. -Word14-Word23-Word31
  58. -Word14-Word23-Word32
  59. -Word14-Word23-Word33
  60. -Word14-Word23-Word34
  61. -Word14-Word24-Word31
  62. -Word14-Word24-Word32
  63. -Word14-Word24-Word33
  64. -Word14-Word24-Word34
  65.  
  66.  
Mar 17 '08 #7

Expert 5K+
P: 8,434
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.
Mar 18 '08 #8

P: 1
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
Nov 1 '11 #9

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

Regards,
Parag Doke
Nov 2 '11 #10

Post your reply

Sign in to post your reply or Sign up for a free account.