Unique combinations

[luvofgreen]

I have placed this in the Office Automation forum already, but read some very intelligent responses in this forum. So I figured I would give it a try, thinking someone maybe able to help me out.


I am new to this site and have been doing a lot of research to find out about combinations and/or permutations. Not sure which way to go except I am leaning towards combinations.

I found code at http://www.vbforums.com/showthread.p...t=combinations that works great as a starting point for me. I have modified it in Excel (see below) to give me the 1287 combinations of A thru M in a 8 spot variation or bucket (from your 6). I am trying to write or find code that will find all of the 2 pair combinations given a certain number of items (sometimes repeating) that can be placed into multiple 8 spot arrays.

My question is - if you can help, can this be used if the letters repeated and used in as many unique 8 spot buckets? For instance, I have (purely example, would change each time) AAAAAABBBCCDEEEEFFFFFGGGGGGHIJJJKKLLLLMMM (41 items) and 8 spots to fill randomly. Theoretically I can get the most 5 buckets of variations. 41/8 = 5. Knowing A and G have 6 items, they would not be able to use the last item. So now there is 39. That will leave one opening ((5 buckets * 8 spots) - 39) anywhere in the 5 buckets.

The other stipulation is 1 letter per bucket so not to be repeated, nor will the letter be paired with the same letter in any of the other buckets. i.e.

Bucket 1 AB CD EF GH
Bucket 2 AC DE FG HI
Bucket 3 AB KL GH ID AB is a BAD pair, and GH is also a BAD pair because they are together in bucket 1 already.

I am writing this in Excel if that helps. Any help would be appreciated.


Mod code.............
Private Sub Command1_Click()

Dim A() As Variant

A = Array("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M")

MakeUniqueCombinationOfSix A

End Sub

Private Sub MakeUniqueCombinationOfSix(AryOfWhat() As Variant)

On Error GoTo MakeUniqueCombinationOfSixError

Dim NCnt1 As Integer, NCnt2 As Integer, NCnt3 As Integer
Dim NCnt4 As Integer, NCnt5 As Integer, NCnt6 As Integer
Dim NCnt7 As Integer, NCnt8 As Integer
Dim UpperBoundsOfArray As Integer, LowerBoundsOfArray As Integer

UpperBoundsOfArray = UBound(AryOfWhat)
LowerBoundsOfArray = LBound(AryOfWhat)

For NCnt1 = LowerBoundsOfArray To UpperBoundsOfArray
For NCnt2 = NCnt1 + 1 To UpperBoundsOfArray
For NCnt3 = NCnt2 + 1 To UpperBoundsOfArray
For NCnt4 = NCnt3 + 1 To UpperBoundsOfArray
For NCnt5 = NCnt4 + 1 To UpperBoundsOfArray
For NCnt6 = NCnt5 + 1 To UpperBoundsOfArray
For NCnt7 = NCnt6 + 1 To UpperBoundsOfArray
For NCnt8 = NCnt7 + 1 To UpperBoundsOfArray
List1.AddItem AryOfWhat(NCnt1) & "," & AryOfWhat(NCnt2) & "," & _
AryOfWhat(NCnt3) & "," & AryOfWhat(NCnt4) & "," & _
AryOfWhat(NCnt5) & "," & AryOfWhat(NCnt6) & "," & _
AryOfWhat(NCnt7) & "," & AryOfWhat(NCnt8)
Cnt = Cnt + 1
Next NCnt8
Next NCnt7
Next NCnt6
Next NCnt5
Next NCnt4
Next NCnt3
Next NCnt2
Next NCnt1
List1.AddItem Cnt
Exit Sub
MakeUniqueCombinationOfSixError:

MsgBox "MakeUniqueCombinationOfSix " & Err.Number & ":" & Err.Description

End Sub

[jemidiah]

Your description of the problem could stand to be a little clearer. As I understand it, you have some string of letters of length N. Those letters happen to be A through M. Your basic operation is this: take the string of letters and mash it down into as many 8-slot buckets as can be completely filled subject to the following constraints--in each 8-slot bucket, no pair may have double letters, and no pair may repeat between buckets.

You want to know how many ways this operation can be performed if the choices are done randomly.


To be honest I'm pretty sure I've gotten some of the details wrong, but like I said your explanation could stand to be clearer. I don't know what meaning most of your sentences intend to convey. I'd be happy to think about the problem, I just need a clear description of the problem designed for someone who hasn't worked with it. One last thing--what does the code you linked have to do with the problem at hand? They seem completely separate.

[luvofgreen]

Understood. I do appreciate the reply greatly.

Let's say I have 13 products of various quantities. And I need to place them in bins with 8 slots where the 2 different products are never paired together, nor is a product repeated in the same bin. I need to fill the available bins as full and uniquely as possible, with as many of the products as possbile, while satisfying the business rules. I am trying to write an excel application, maybe Access to increase efficiencies.

So in the scenario above I have 41 totals items and based on the business rules described above, I believe I can get 5 bins filled with one spot left open. Now I would like to get a "report" or listing of all of the different variations that are possible. Again, using as many of the products so that only the bare minimum are left over.

Then I would fill bins based on the results. Hope this is clearer.

The key is to build unique pairs and fill in the 8 spots, satisfying the above rules

Example result would be:
AAAAAABBBCCDEEEEFFFFFGGGGGGHIJJJKKLLLLMMM

AB CD EF GH NOTE: D is used up - can't be used again
AC LF EG IJ NOTE: C and I are used up
FK LM AG "Open Spot" J
FL EA BG MJ NOTE: E is used up
FA GL EM KB NOTE: A and G are left over because there were 6 each

NOTE: I do this manually, so there maybe an error in pairings
AG

[jemidiah]

That seems to be a complicated question. My first impulse is to brute force it but that would end up with an obscene number of possibilities if the number of item types is large. What are the restrictions on open slots?


Here are my thoughts so far:
Fill the first bucket with 1 of the possibilities your routine above gives. This can be done in (13 choose 8) = 1287 ways. However, the routine you have lists them in index-increasing order. For instance, it'll only generate ABCDEFGH and not BACDEFGH. Much of the time this won't matter, since you'll have the same pairs, but sometimes it will matter--for instance your routine will never generate the pair AM. However your routine can still be used to pick 8 item types out of your 13. From there you can generate a bucket by picking 4 pairs. You could do this by assigning an arbitrary order to the 8 item types which can be done in 8! = 40320 ways, though I'm assuming the order of items in a pair doesn't matter, and the order of the pairs doesn't matter. Divide off 2^4 to account for pair inversions, and 4! for pair orders. Thus there are 1287*8! / (2^4 * 4!) = 135135 different buckets.

Now we have 1 bucket filled. Remove those 8 items from the list and make a new bucket--but there are fewer ways to fill this bucket. We don't want any repeat pairs, so when we generate pairs we have to check to see if that pair has been used. There is no easy analysis to figure out how many buckets of this type there will be, probably in the tens of thousands. Repeat until all 5 buckets are filled--though I don't know how to handle open slots yet.

Assuming the order of the buckets themselves doesn't matter, we'll get many equivalent solutions--size 5! = 120 equivalence classes, in fact. That just means we'll divide the number of solutions by 120, though; there are probably hundreds of millions even then.

So, with the number of solutions to your problem, I have to ask--is this really what you want? A list of many millions of solutions? Or is something missing?

[luvofgreen]

Thanks for the reply. Very informative and thorough.

Wow, the things that must fly through your mind when you are surrounded by silence Pls don't take that the wrong way. I just never thought my scenario was so complex, and more importantly would generate so many different concepts that I never heard of, yet you speak about it with such ease. I may have bitten off more than I can chew.

As for the questions, the empty slot can be in any of the buckets, but I try to not have more than one in each bucket. It is better to have a empty slot than not have a repeat product. It also can be in any of the pairs in any of the buckets.

One promising note that you alluded to was the (13 choose 8), my research was leading me there as well. I was thinking there would around 1200-2800 variations that would be generated based on the # of products produced that week.

As for the Product order (AAAAAABBBCCDEEEEFFFFFGGGGGGHIJJJKKLLLLMMM), I simply indexed it for simplicity and example sakes. To clarify, it doesn't matter the order they are placed in the bucket. I was actually thinking that they would be placed in the buckets in a logical order. But as long as they meet the business rules. Does that help matters greatly?

<snip>though I'm assuming the order of items in a pair doesn't matter, and the order of the pairs doesn't matter<snip> The pair order and order of pairs definitely do not order.
So based on that can we ignore the 135135 buckets? I think I can keep it at the "simple" 1287 for my situation.

As for the analysis of previous pairs, I was thinking about assigning the pairs in a logical order, then shuffling each bucket to give the appearance of randomization. Let's say the # of products would vary week after week, but they would always be placed in the same order until the products run out. For instance with AABBBCDEEEEFFGGHHIJKKK (again they can appear in any order, just doing for simplicity), A would be placed in 2 different buckets, typically 1 and 2. Product B, 3 times in buckets 1, 2 and 3. Product C goes in only 1 bucket, probably #1, and so on. Then I would shuffle the buckets, though I am not sure if I really need to do that now.

Are you a programmer by chance? Because as I was visualizing this, I was was trying to figure out the best way to remove the items that were chosen for each bucket. It makes sense that it needs to be done. But do I rebuild the string, and then run it through the code again to build a 2nd bucket? Or should my code take that into account. Or should I consider another Array and subtract each applicable element by one when it is assigned? Again I understand you may not know, but throwing it out there.

So to summarize, I definitely do not want a million solutions. I was thinking that there was a way to write a program so that I do not have to do this and can go on to other things, like understand what Equivalence Classes are I tried to google it and again I am at awe with your knowledge!

Anyways, I would have a program that I put in the quantity of each of the X # of different products. I would push a button and it would give me the listing of X choose 8 results. Then when I have the results, I would go to into another analysis to see where i can go from there.

Truly your insight and help are appreciated. And if this is too complex I do understand.

[jemidiah]

So based on that can we ignore the 135135 buckets? I think I can keep it at the "simple" 1287 for my situation.

Unfortunately not. The "simple" 1287 buckets ignores a very large number of possible buckets. For instance, AM BC DE FG isn't one of those 1287 buckets, nor can you make it one by reordering and flipping the pairs in any of those buckets. You have to use all 135135 buckets to get AM BC DE FG. In fact there are (13 choose 8)*8! ~= 52 million arrangements of sets of 8 out of 13 items. It goes down to only 135135 because flipping the pairs and reordering them doesn't matter--that is to say, BC MA DE GF is the same as AM BC DE FG, so only one of those two gets to be one of the 135135 buckets.

The algorithm you linked that generates your groups of 8 arbitrarily imposes a constraint: that your groups be in alphabetical order. This gives the illusion of having "unordered" groups of 8. That is, it doesn't generate both ABCDEFGH and BHFEDCBA, since, when they're unordered, they're the same group. The "choose" function (binomial coefficient) counts unordered groups, but your application requires some semblance of order. Since each of the 1287 unordered groups can be paired off in multiple ways (105, to be precise) you have a whole bunch more ways to make a bucket.

As for the analysis of previous pairs, I was thinking about assigning the pairs in a logical order, then shuffling each bucket to give the appearance of randomization. Let's say the # of products would vary week after week, but they would always be placed in the same order until the products run out. For instance with AABBBCDEEEEFFGGHHIJKKK (again they can appear in any order, just doing for simplicity), A would be placed in 2 different buckets, typically 1 and 2. Product B, 3 times in buckets 1, 2 and 3. Product C goes in only 1 bucket, probably #1, and so on. Then I would shuffle the buckets, though I am not sure if I really need to do that now.

The algorithm you're describing is vastly different from one that produces every possible solution to your constraints. It might well work (though in some edge cases it wouldn't).

Are you a programmer by chance? Because as I was visualizing this, I was was trying to figure out the best way to remove the items that were chosen for each bucket. It makes sense that it needs to be done. But do I rebuild the string, and then run it through the code again to build a 2nd bucket? Or should my code take that into account. Or should I consider another Array and subtract each applicable element by one when it is assigned? Again I understand you may not know, but throwing it out there.

I am a programmer . I would use arrays, heavily, that count the number of items of each type. At the start of "assembling" a set of buckets, I would copy my initial array and decrement that as I assemble. When I finish assembling the set of buckets, I would print it out (or do whatever you want to it) and discard the copy, since it's probably empty and definitely useless. Strings would almost certainly be a bad idea because of their slowness. I'm envisioning an optimization problem over millions of solution states--you don't want string functions slowing that down or it'll take over a week to optimize it, which is probably longer than you want.

Anyways, I would have a program that I put in the quantity of each of the X # of different products. I would push a button and it would give me the listing of X choose 8 results. Then when I have the results, I would go to into another analysis to see where i can go from there.

Is it particularly important that your constraints be satisfied exactly? For instance, if your company makes or loses $50,000 for a mismatched pair, if I were you I would find a way to generate every solution (all however-many-million of them) and figure out the best solution based on lowest cost. If it's less important (sounds like it) I would just implement the algorithm you described in the quote above, which will do a decent job much of the time and will leave you to fill in a few blanks at the end.

There's also another possibility. You could use random numbers to assign all of your items vaguely intelligently, and use the magic of repeated random trails to get a good satisfying assignment with high probability. To be more specific... start by figuring out how many items will be used in how many buckets (which are both relatively easy things to automate). Choose one of those items randomly for the first slot of the first bucket. Choose another for its pair--and keep track of the pairs you've generated; if you happen to choose the same item type, pick another item until you get a pair of two different items. Randomly choose the third slot of the first bucket, taking care to get a different item again. Continue in this fashion until the first bucket is full. For the second bucket, do the same thing except add one more check--whenever you're about to make a pair, make sure it hasn't been made yet. Throw in blank buckets as you feel like, since I'm still not quite sure where they belong.

After a while you'll generate a full, satisfying arrangement. One thing of note, though--sometimes your random choices will conspire against you and make you infinitely loop, trying to complete an arrangement that can't satisfy all requirements. To get around this you'll want to give only so many tries at each "do it again until it works" step before you toss the entire thing out and start again from scratch. When you start again you could print what you have, and maybe your human brain will see a quick transposition or something to make everything work well. Or, you could just have it try again, and you could have it continue trying until it works, or mostly works.

Your question is remarkably complicated for the relatively simple setup. One thing to remember in computers is that doing something visually, especially if it involves a logic puzzle, can usually be done very easily by a human but is very difficult for a computer. Consider Chess or Checkers; you can "see" most of the moves, but to program a computer to play either is difficult, and to program a Chess game that can beat a human grandmaster is awful. Our brains pick out patterns naturally, but figuring out how to get a computer to do the same is often horrendous.

[luvofgreen]

Thank you very much for your time and energy. I am going to digest everything now.

[jemidiah]

I can be more explicit if you'd like. As it was I breezed past the first few weeks of a combinatorics course that you probably never had.