# Finding possible combinations & listing the wanted combinations

1. ## 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. ## 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.``

3. ## 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. ## 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.

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

6. ## 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. ## 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. ## Re: Finding possible combinations & listing the wanted combinations

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

9. ## 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

10. ## 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. ## 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?

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. ## Re: Finding possible combinations & listing the wanted combinations

Your lucky number is 6:

should have the combinations you need.

abousetta

14. ## 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. ## 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. ## Re: Finding possible combinations & listing the wanted combinations

Here is the file.

abousetta

17. ## 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. ## 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. ## 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!

20. ## 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.``

21. ## 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. ## 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. ## 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. ## 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)

25. ## 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.

26. ## 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:

27. ## 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.

28. ## 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.

29. ## 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. ## 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. ## 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.

##### Users Browsing this Thread

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

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