+ Reply to Thread
Results 1 to 31 of 31

Finding possible combinations & listing the wanted combinations

  1. #1
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Finding possible combinations & listing the wanted combinations

    Hello. As you can see I am new to this forum. I hope someone can help me with my problem. I'll try to explain the data I am using and what I need, although it's a bit difficult to explain. Especially since I do not use Excel very often. This is what I have:

    Please Login or Register  to view this content.
    Each person always gets 5 checks/trues (or a '1' in this case) out of 20, I need to find which 4 people will make a full row of 20 true's, and if that combination doesn't exist, which 5 people. It would be great if it could show multiple combinations, first the 4 people combinations, then the 5, etc. But just the 4 people combination is sufficient.

    I hope someone understands what I need and hopefully someone knows how to get it. Thanks in advance!

  2. #2
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    If the number of columns will remain at twenty, this code will give you a message box with the four or five names needed. If it can't be done with five then the message will be "No Matches Found" like in the example you posted (since you would need all six names to complete the set):

    Please Login or Register  to view this content.
    Please consider:

    Thanking those who helped you. Click the star icon in the lower left part of the contributor's post and add Reputation.
    Cleaning up when you're done. Mark your thread [SOLVED] if you received your answer.

  3. #3
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    Thank you for the time you put into this, abousetta! Since I'm quite a beginner with Excel, would it be too much trouble to ask if you could put this into an excel file for me to test and copy this? Thanks again for this!

  4. #4
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    Sorry about that. Have a look at the attachment. The code is in a vba standard module. You can see this by clicking Alt + F11 and you see the macros in your open workbooks there or by clicking Alt + F8. In the example, I have added a button for ease of running but if you transfer the code to your another workbook then you will need to create a way to access it (e.g. button or manually or many other ways depending on your needs).

    Two things to remember, you can have as many rows as you would like but only 21 columns (one for names and 20 for data). If you need this adjusted then let me know.

    Hope this helps.
    Attached Files Attached Files

  5. #5
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    Excellent. Thank you for the file and the detailed explanation. I've downloaded the file and put some test values in it but when I hit the button it freezes up. Am I doing something wrong? I'll upload the file with test values so you can see if you get the same result.
    Attached Files Attached Files

  6. #6
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    The number of permutations increases exponentially each time you add more people. Let me see if I can add a progress meter so you can see how long it will take and tweak it a bit further.

  7. #7
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    OK, abousetta. I'll let it run for a while. Currently I have as many people in the real file as I have in the test file so I'll look how long it takes to get results with this. Thank you again and if you do get to tweak it, I'm looking forward to try the tweaked version as well!

  8. #8
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    It's still running. It does take quite a while.

  9. #9
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    I generated a quicker version and ran it. It took 26 minutes to run (even though it is now slowed down by a progress meter), but found no matches. So the million dollar question is... was this the answer you were looking for?

    abousetta
    Attached Files Attached Files

  10. #10
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    Thank you again, abousetta! I've just downloaded it to give it a try! Is it not giving a result with either a 4 or 5 people combination? How difficult would it be to add a 6 people combination?

  11. #11
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    Here's an updated version. I will try to run it from my end later today just to see what happens.

    Please Login or Register  to view this content.
    Do you have a limit on this or you going to keep running until you get a match?
    Last edited by abousetta; 07-10-2012 at 06:47 PM. Reason: forgot one of the Nexts

  12. #12
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    Great! I'll give this a try too. I can run it a day before so time is no issue if that's what you meant.

  13. #13
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    Your lucky number is 6:

    Abel, Abie, Acey, Adam, Alba, Brad

    should have the combinations you need.

    abousetta

  14. #14
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    I get a compile error "For without next" when I copy and paste it. Do you have it in a .xlsm‎?

  15. #15
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    Yes, I forgot one of the nexts. I added it to the code above. There should be five Next: instead of four.

  16. #16
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    Here is the file.

    abousetta
    Attached Files Attached Files

  17. #17
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    Wonderful. Works great and very fast! Does it show the first possible combination or does it show all possible combinations with this being the only one? Not to worry, just one is excellent. Just wondering if it's the only possible combination.

  18. #18
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    Actually there was a flaw in the design of the last version. It started looking at 6 combinations instead of 4 then 5 then 6. I am testing a new version right now that should also be printing the results to another sheet.

    Probably be back tomorrow with the results.

  19. #19
    Forum Expert mikerickson's Avatar
    Join Date
    03-30-2007
    Location
    Davis CA
    MS-Off Ver
    Excel 2011
    Posts
    6,229

    Re: Finding possible combinations & listing the wanted combinations

    Hmm...I'm working on my own angle, but... to speed up the search..
    Consider if you have N people, that code is searching through all N(N-1)(N-2)...combinations.

    That number can be made smaller if one first finds the column with the fewest number of 1's, call than number K.
    We know that one of those K people must be in the solution. Thus requiring only K(N-K)(N-K-1)... loops.
    If we are looking for 5 or more folks, that increases to K(N-1)(N-2)... (its possible that the only 5 solution includes two of the K people), in either case its less than N!
    _
    ...How to Cross-post politely...
    ..Wrap code by selecting the code and clicking the # or read this. Thank you.

  20. #20
    Forum Expert mikerickson's Avatar
    Join Date
    03-30-2007
    Location
    Davis CA
    MS-Off Ver
    Excel 2011
    Posts
    6,229

    Re: Finding possible combinations & listing the wanted combinations

    Here's my effort.
    Its a brute force approach that uses bit wise OR to test possibilites.
    With the data from post #16, it takes about 1min 40s to find (and list) the first combination.

    As written, it will write out all solutions of 4 names (if they exist) and stop. OR write out all solutions of 5 names and stop OR write out the first solution of 6 names and stop before trying to loop through all 5,000,000 possibilities of 6.

    There has to be a better way to do this than brute force.

    Please Login or Register  to view this content.
    Attached Files Attached Files
    Last edited by mikerickson; 07-11-2012 at 01:18 AM.

  21. #21
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    Ok abousetta. It's no issue for now but later when more names are added it might.

    Thank you, mikerickson! I understand that it takes too long and that there are possibly too many possible combinations with 6 names but would it be difficult to let it show the maximum possible 6 name combinations without using duplicate names?

  22. #22
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    Mike is right, there has to be a better way. I am attempting to sort the columns first by frequency then running the algorithm but still running into hours of run-time. Also just to note @zoke your dummy workbook is a bit off with the total score for some names not being 5 (from 0 to 7 I believe). Not that it matters right now but in real life we need to know if it's giving the right results or not.

  23. #23
    Forum Expert mikerickson's Avatar
    Join Date
    03-30-2007
    Location
    Davis CA
    MS-Off Ver
    Excel 2011
    Posts
    6,229

    Re: Finding possible combinations & listing the wanted combinations

    To find a better way, could we take one step back and ask what the purpose of this is?
    Once we know that purpose, we could ask if there some (better) way to achieve that purpose other than the current approach of assigning 20 characteristics to each person and searching for a combo.

    "would it be difficult to let it show the maximum possible 6 name combinations without using duplicate names?"
    If you mean that you want to know how many 6 name combinations meet the criteria, no it wouldn't be difficult, just slow.
    (BTW, in re: "without using duplicate names". In this situation, duplicating a name doesn't get you closer to the criteria, so that isn't a consideration.)

    If you mean that you want to know how many possible 6 name combinations there are from your list of names (without regard to the criteria),
    that would be =COMBIN(N, 6) where N is the number of names. (aka "lots and lots")

  24. #24
    Forum Expert mikerickson's Avatar
    Join Date
    03-30-2007
    Location
    Davis CA
    MS-Off Ver
    Excel 2011
    Posts
    6,229

    Re: Finding possible combinations & listing the wanted combinations

    I think I have a logic that will work.

    Consider a similar case.
    There are 11 names, and 6 columns
    Each of name has two 1's in its row.

    Find the triplets of names who, when combined, have a one in every column.

    Consider the data set


    Please Login or Register  to view this content.
    Note that in the first column, only Abe and Carl have a one.

    Therefore, any solution will have either Abe or Carl as one of the names in the solution.

    Consider Abe 1 0 1 0 0 0

    The first 0 is in the second column.
    Barb and George are the only names that have a 1 in the second column.

    If Abe is in a solution, then either Barb or George must also be in that solution.

    Consider
    Abe, Barb = 101000 OR 010010 = 111010

    The fourth column is the first 0, in which column George and Hera have 1's.

    Thus,
    (Abe, Barb, George)
    (Abe, Barb, Hera)
    are possible triplet solutions

    That takes care of Abe, Barb.

    Next consider Abe, George
    Abe,George = 101000 OR 010100 = 111100

    The fifth column (lowest 0) gives us three more possible triplet solutions.
    (Abe, George, Barb)
    (Abe, George, Carl)
    (Abe, George, Earl)

    We are done with Abe,George and, hence Abe.

    Look at Carl 100010

    Barb, George in column 2 give us

    Carl,Barb = 100010 OR 010010 = 110010
    Column 3 gives us (Carl,Barb,Abe) (Carl,Barb,Earl) (Carl,Barb,Fiona)

    Carl,George = 100010 OR 010100 = 110110
    Column 3 gives us (Carl,George,Abe) (Carl,George,Earl) (Carl,George,Fiona)

    These 11 possible solutions are fewer than 20 (6 choose 3)
    Last edited by mikerickson; 07-12-2012 at 06:10 AM.

  25. #25
    Forum Expert mikerickson's Avatar
    Join Date
    03-30-2007
    Location
    Davis CA
    MS-Off Ver
    Excel 2011
    Posts
    6,229

    Re: Finding possible combinations & listing the wanted combinations

    I think I have a logic

    Please Login or Register  to view this content.
    The Combine function would have to deal with both the names of the (possible) solution and the value of that solution.
    Last edited by mikerickson; 07-12-2012 at 06:11 AM.

  26. #26
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    abousetta, you are correct. There were a few incorrect values in the test sheet. I'll upload a workbook with correct values:
    Attached Files Attached Files
    Last edited by Zoke; 07-12-2012 at 06:13 AM.

  27. #27
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    OK. I have a modified version which checks combinations using 4, 5 or 6 names. It took me around 30 minutes to run but generated almost 150,000 possible combinations. I haven't had a chance to check them out yet but thought it might stimulate the discussion to post what I have so far.

    abousetta

    P.S. I erased them except the first 10 as an example to cut down the file size.
    Attached Files Attached Files

  28. #28
    Forum Expert mikerickson's Avatar
    Join Date
    03-30-2007
    Location
    Davis CA
    MS-Off Ver
    Excel 2011
    Posts
    6,229

    Re: Finding possible combinations & listing the wanted combinations

    I coded the logic explained above.
    It takes about 30 seconds to find the 147,056 solutions from post #23 data and displays them 1000 at a time.
    Attached Files Attached Files

  29. #29
    Forum Guru
    Join Date
    03-12-2010
    Location
    Canada
    MS-Off Ver
    2010 and 2013
    Posts
    4,418

    Re: Finding possible combinations & listing the wanted combinations

    Good for you Mike. I definitely want to compare our codes since you practically dropped a 30 minute operation to 30 seconds.

  30. #30
    Forum Expert mikerickson's Avatar
    Join Date
    03-30-2007
    Location
    Davis CA
    MS-Off Ver
    Excel 2011
    Posts
    6,229

    Re: Finding possible combinations & listing the wanted combinations

    It helps to think of the clsCombination property .Value as a binary number, corresponding to columns of data.

  31. #31
    Registered User
    Join Date
    07-10-2012
    Location
    Netherlands
    MS-Off Ver
    Excel 2010
    Posts
    12

    Re: Finding possible combinations & listing the wanted combinations

    Thanks guys! I am away for a week but I'll definitely try these when I'm back home.

+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Bookmarks

Posting Permissions

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

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1