Combination algorithm for indefinite string arrays

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • paragpdoke
    New Member
    • Dec 2007
    • 62

    Combination algorithm for indefinite string arrays

    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
    New Member
    • Dec 2007
    • 62

    #2
    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.
    Code:
    Arr1    Arr2    Arr3    ...  ArrN
    S11     S21     S31     ...  SN1
    S12     S22     S32     ...  SN2
    S13     S23     S33     ...  SN3
    .       .       .       .    .
    .       .       .       .    .
    .       .       .       .    .
    S1A     S2B     S3C     ...  SNX

    Comment

    • kadghar
      Recognized Expert Top Contributor
      • Apr 2007
      • 1302

      #3
      Originally posted by 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
      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.

      Comment

      • Killer42
        Recognized Expert Expert
        • Oct 2006
        • 8429

        #4
        Originally posted by kadghar
        ... 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...
        Code:
        Determine the number of columns, [B]c[/B].
        Define a numeric array [B]ColLength[/B] with [B]c[/B] entries.
        Define an identical numeric array [B]ColPos[/B] with [B]c[/B] entries.
        Populate [B]ColLength[/B] array with the number of entries in each column.
        Set all the elements in the [B]ColPos[/B] to 1.
        In an "infinite" loop...
          Concatenate the cells pointed to by all the entries in [B]ColPos[/B] array.
          Increment entry [B]c[/B] in your [B]ColPos[/B] array.
          If [B]ColPos(c)[/B] > [B]ColLength(c)[/B] Then
            Set [B]ColPos(c)[/B] back to 1
            Increment the next ColPos entry to the left
          End If
          Continue this sequence all the way to the left...
          If all [B]ColPos[/B] entries have reached their corresponding [B]ColLength[/B] 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.

        Comment

        • paragpdoke
          New Member
          • Dec 2007
          • 62

          #5
          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

          Comment

          • Killer42
            Recognized Expert Expert
            • Oct 2006
            • 8429

            #6
            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?

            Comment

            • paragpdoke
              New Member
              • Dec 2007
              • 62

              #7
              Originally posted by 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?
              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.]
              [CODE=vb]
              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 GenerateCombina tions(vbNullStr ing, WordsCol)
              Debug.Print IteratorString
              Next IteratorString

              End Sub

              Function GenerateCombina tions(CurrentSt ring As String, NextCollection As Collection) As Collection
              Dim IteratorString As Variant
              Dim ReturnCollectio n As New Collection
              Dim CurrentCollecti on As Collection
              Set CurrentCollecti on = NextCollection. Item(1)
              If NextCollection. Count > 1 Then
              NextCollection. Remove (1)
              For Each IteratorString In CurrentCollecti on
              Dim NextIterator As Variant
              For Each NextIterator In GenerateCombina tions(CurrentSt ring & "-" & CStr(IteratorSt ring), NextCollection)
              ReturnCollectio n.Add NextIterator
              Next NextIterator
              Next IteratorString
              NextCollection. Add CurrentCollecti on, , 1
              Else
              For Each IteratorString In CurrentCollecti on
              ReturnCollectio n.Add CurrentString & "-" & CStr(IteratorSt ring)
              Next IteratorString
              End If
              Set GenerateCombina tions = ReturnCollectio n
              Set ReturnCollectio n = Nothing
              Set CurrentCollecti on = Nothing
              End Function

              [/CODE]
              The output:
              Code:
              -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
              Last edited by Killer42; Mar 18 '08, 01:43 AM. Reason: Changed CODE tage to CODE=vb

              Comment

              • Killer42
                Recognized Expert Expert
                • Oct 2006
                • 8429

                #8
                Originally posted by paragpdoke
                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.

                Comment

                • frajag
                  New Member
                  • Nov 2011
                  • 1

                  #9
                  Help

                  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

                  Comment

                  • paragpdoke
                    New Member
                    • Dec 2007
                    • 62

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

                    Regards,
                    Parag Doke

                    Comment

                    Working...