Results 1 to 14 of 14
  1. #1
    3 Star Lounger
    Join Date
    Jan 2001
    Location
    Melbourne, Victoria, Australia
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts

    All possible strings of n distinct words function? (Office 2000 / SP2 and VBA)

    I'm looking for a way to generate, in VBA code, all possible strings that you can make, of any length, and only using each word once, from a set of n distinct words. For example if the set were {hot, cold, wet} then you can have {{hot,cold},{wet}} or {{hot, wet},cold}} etc, etc (five distinct possibilities with three words)
    Does anyone have a clue how to go about this.
    In fact, more ambitiously, I want a custom function procedure whose argument is, say, an array of n (unspecified number) distinct strings and whose out put is a recordset of all possible sets of strings using only the strings contained in the array's argument.But if anyone can suggest a direction to go with this for the simpler first part I'd be very grateful!
    Thanks

  2. #2
    5 Star Lounger Ruff_Hi's Avatar
    Join Date
    Feb 2001
    Location
    New York, New York, USA
    Posts
    768
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    In short, you need some form of bubble sort based routine. To illustrate, suppose you have 4 words - call them 1, 2, 3, 4. Then you can have a total of 24 different combinations - 4 x 3 x 2 x 1 = 24. If you only want a output length of 2 words then you have a total of 12 combinations (4x3).

    You need to think in terms of an array of length n with each word held in one element of the array. Thus we have an array with n words (ie n elements). Each element is referenced by an index (1 thru n).

    Now you want a function that takes the kth (where k = n-1 to start with) index value (in the above example '3') and increases it by 1 (checking that that index value is not used in positions 1 thru k-1. If it is, then increase it again and check again. If the value of the kth index > n then go back one index value (ie k = k-1) and try to increase that value. If the function cannot increase any index value, then you should have reached the end.

    Once you have successfully increased the kth index, reorder the k+1 to nth index in ascending order and output the result.

    Then call this function again with the new array that you just formed. Stop calling the function when you get an array of n, n-1, n-2, ..., 3, 2, 1.

    Clear as mud? Consider the following example:

    1234 -> into function yields 1243 (output result and use this value as the new input into the function)
    1243 -> into function yields 1324
    1324 -> into function yields 1342
    1342 -> into function yields 1423
    1423 -> into function yields 1432
    ...
    4312 -> into function yields 4321
    4321 -> function cannot increase any index
    (Location Australia, then UK, but now USA. Heart, outlook, attitude, etc always Australian)
    Quote: "All Happiness is the release of internal pressure"

  3. #3
    Plutonium Lounger
    Join Date
    Dec 2000
    Location
    Sacramento, California, USA
    Posts
    16,775
    Thanks
    0
    Thanked 1 Time in 1 Post

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    <hr>and whose out put is a recordset of all possible sets of strings using only the strings contained in the array's argument<hr>
    You want a recordset that only contains specific string? Or do you want one that only contains records that contain specific strings? And are the string in question the ones you specified in your post? Or are you, in fact, looking for records that contain the *words* in those strings in any combination?

    If you want all the records that contain some combination of the words hot, cold and wet, then try the advice already posted. If you just want records that contain at least one of those words, just use the In operator, i.e., In ("hot","cold","wet").
    Charlotte

  4. #4
    3 Star Lounger
    Join Date
    Jan 2001
    Location
    Melbourne, Victoria, Australia
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    Thanks Charlotte. In my youth I could solve these problems in a snap but the neurons don't fire as well these days. Your comments are good but I'm not sure if I'm gettting my message clear.
    What I really want is this:
    A customer comes into my cafe and orders a salmon foccaccia and a coffee. (verbally, no paper, no table numbers). This is entered into my computer as
    order number 413 comprising order detail 1009 = 'Salmon Foccaccia' and Order number 413 order detail 1010 = 'coffee' in the linked tables 'Orders' and 'Order details'.They sit down and comsume same.
    Later they say to a waiter, as she passes by, "Oh, another coffee please!" But the waiter blithely enters this into the computer as order number 428 order detail number 1066 = 'coffee.' When they come to pay
    they say "I had a foccaccia and two coffees". They, like most people, are too indolent to say what kind of foccaccia or tell you that they ordered the second coffee separately. All I have is the information
    {foccaccia, coffee, coffee} like my {hot, cold, wet}.
    So I want the system to generate all possible mutually exclusive and exhaustive subsets of the set {foccaccia, coffee, coffee} where we pretend that the elements 'coffee' and 'coffee' are actually distinct for the nonce. There are in fact 5 possibilities: all three appear against one order number ( one possible choice), two appear against one order number and the third against another (3 choices) and each one appears against it's own distinct order number (one choice again). Using the like operator the system searches through all unpaid orders (order numbers with at least one order detail not paid for) for all possible matches to each of the 5 possibilities above.
    Of course it won't be 5 if the customer says four things, it will be 18 possible arrays, etc as the numbers grow.
    But let's stick with the case of three words giving five possible corresponding arrays for now.
    For each such array there will be zero or more matching arrays of order numbers. Among these possibilies is buried the true one, viz {413, 428}.
    So I want my function to return the set of all arrays of all possible order number combinations which correctly match the 5 possible arrays of the words
    foccaccia, coffee, coffee and THEN I wil try to rank them in desceding order of likelikhood and display them on my pay screen form.
    I hope this isn't all too much!
    The operator will then cast her eye down this display and hopefully located the correct order combination
    for the customer.
    I need this complicated setup because it is not appropriate to the style or modus operandi of our establishment to use any of the conventional restaurant odering systems based on table numbers, portable order number tickets or anything so formal.
    We are a VERY relaxed corner village shop and the customers would think we were turning into a MacDonald's or something if we tried this.
    If you have an inspired suggestion if would really help
    as my experience with VBA and function procedures is still in its infancy!

  5. #5
    Plutonium Lounger
    Join Date
    Dec 2000
    Location
    Sacramento, California, USA
    Posts
    16,775
    Thanks
    0
    Thanked 1 Time in 1 Post

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    You lost me in there somewhere. If the server enters the second coffee with the wrong order number, I don't see how you can ever find the right order as you described it. I'm sorry, but even the way you operate is making my head spin. <img src=/S/dizzy.gif border=0 alt=dizzy width=15 height=15> I'd opt for an "unfriendly" order pad.
    Charlotte

  6. #6
    3 Star Lounger
    Join Date
    Jan 2001
    Location
    Melbourne, Victoria, Australia
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    The right order can be found in theory because unless two orders or two "pairs" of orders are identical then the customer will say "I didn't have that" or " and I had something else". If the orders are identical then I won't care if they are mixed up. We've tried order pads and it was a monumental headache! We keep reverting to "Oh! What did you have then?".
    Sorry to make your head spin Charlotte!
    I guess you wouln't want a job in our cafe now! <img src=/S/sad.gif border=0 alt=sad width=15 height=15>
    I'm determined to figure something <img src=/S/devil.gif border=0 alt=devil width=15 height=15> out but my head feels like it's about to spin off as well.
    Maybe I'll just have a coffee and relax... <img src=/S/flee.gif border=0 alt=flee width=25 height=25>
    David

  7. #7
    Super Moderator jscher2000's Avatar
    Join Date
    Feb 2001
    Location
    Silicon Valley, USA
    Posts
    23,112
    Thanks
    5
    Thanked 93 Times in 89 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    You're serious! I thought the toasted bagel examples were hypothetical, and it was probably more like threaded sprockets. <img src=/S/smile.gif border=0 alt=smile width=15 height=15> I like food. Food is good.

    I recently had to pair an arbitrary number of strings, but only into pairs. Doing this manually for 12 different codes was too much, so I wrote this procedure:

    <pre>Sub StringPairer()
    'Copyright 2001 Jefferson Scher
    Dim strUser As String, strArray() As String
    strUser = InputBox("Enter items to pair, separated by commas (e.g., A,B,C)")
    If strUser = vbNullString Then
    MsgBox "Bye!"
    Exit Sub
    ElseIf InStr(1, strUser, ",") = 0 Then
    MsgBox "No commas found, so there's only one item and you don't need me. Bye!"
    Exit Sub
    End If
    strArray() = Split(strUser, ",")
    Dim docNewDoc As Document, i As Integer, j As Integer
    Set docNewDoc = Documents.Add
    With docNewDoc.Range
    For i = 0 To UBound(strArray)
    For j = i + 1 To UBound(strArray)
    .InsertAfter "(" & strArray(i) & " and " & strArray(j) & ")[SRCHCODE] "
    .InsertParagraphAfter
    Next j
    Next i
    End With
    End Sub</pre>

    Note that this runs in Word because this list would require further editing.

    Let's take the example of A,B,C,D,E. For my purposes, I did not want to pair A with A, because I was searching a database and matching A alone was not relevant. However, you do want to pair A with A, because 2 bagels is relevant. In my code, making the j loop start at i+1 skipped the A+A, you will want to start your j loop at i. The difference is illustrated in the crude drawing I have attached: I wanted the green squares, and you want both the green and red squares.

    To expand this approach to n dimensions really is asking a lot. There are people capable of thinking in recursive code who could develop a more elegant solutions, but I'd be inclined to just have a number of different loops to handle up to, say, 5 items. Beyond that you would have so many loops, well, it just seems nutty.

    Well, this doesn't even address the further complication that you want to account for all of the items in each result set. Now I have a headache.
    Attached Images Attached Images

  8. #8
    3 Star Lounger
    Join Date
    Jan 2001
    Location
    Melbourne, Victoria, Australia
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    Of course I'm serious! Now your discussion is very interesting but it's too late for me to concentrate on it tonight but I'll look at it in detail tomorow. Suffice to say I went back to my old university library today and dredged up some treatises on combinatorics including relevant topics on Stirling numbers and Bell numbers. All very weird but definitely related to this discussion. Back soon...

  9. #9
    Super Moderator jscher2000's Avatar
    Join Date
    Feb 2001
    Location
    Silicon Valley, USA
    Posts
    23,112
    Thanks
    5
    Thanked 93 Times in 89 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    Here's some code for a small number of items (3-5). Maybe there is a way to generalize from this, but it's beyond my current paradigm.
    Attached Files Attached Files

  10. #10
    3 Star Lounger
    Join Date
    Jan 2001
    Location
    Melbourne, Victoria, Australia
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    Actually your example is quite accurate in my case for pairs because in your coloured boxed example both
    A and B are equal to "bagel" so the j loop can start at i+1 too. I know it's pretty involved what I'm trying to do but I'm determined to get there!

  11. #11
    3 Star Lounger
    Join Date
    Jan 2001
    Location
    Melbourne, Victoria, Australia
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    Great Job! It works correctly for 3 or 4 items but something goes wrong with five items. I will check closely to see why. But the Pascal triangle for Stirling Numbers shows that there are 52 possibilities for five items and the code only generates 42. But it's very helpful and on the right track. See attached "photocopy" for your interest.
    Attached Images Attached Images

  12. #12
    Super Moderator jscher2000's Avatar
    Join Date
    Feb 2001
    Location
    Silicon Valley, USA
    Posts
    23,112
    Thanks
    5
    Thanked 93 Times in 89 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    That graphic is unreadable for me; I think it lost something in the compression. If you look at these colorful pictures, you'll see what I missed: sets of 3 plus the 2 others as individual buckets. Maybe I should have taken more math.

    <A target="_blank" HREF=http://forum.swarthmore.edu/advanced/robertd/stirling2.html>http://forum.swarthmore.edu/advanced...stirling2.html</A>

    (His group of 25 contains the 10 3-1-1 solutions mixed together with the 15 2-2-1 solutions.)

  13. #13
    3 Star Lounger
    Join Date
    Jan 2001
    Location
    Melbourne, Victoria, Australia
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    Yes I realised that you missed the 3, 1,1,1 situation.
    Thanks for the reference, I'll look into it.

  14. #14
    3 Star Lounger
    Join Date
    Jan 2001
    Location
    Melbourne, Victoria, Australia
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: All possible strings of n distinct words function? (Office 2000 / SP2

    Actually, I independently looked up the same page one hour ago before you told me so we're definitely thinking along the same lines. Don't worry about your math: it is fine and I'm qualified to say this as I earned my Ph. D. in Maths in '78. Pity it has all deserted me now!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •