Permutations of a list (groups of 3)

Is there any way to determine all possible unique combinations (or sets) of any 3 strings in a table? I need to make a master set list from a list of strings which could be over 100 elements long.

Once I have a result set, I need to get rid of any groups which have a value contained in another group.

Example:
cells A1 through B100 contain:
Item1 45
Item2 50
Item3 98
...
Item100 75

Result set would contain groups of any 3 item combinations where the corresponding "B" value is within a certain range (between 40 and 80), while also trying to create sets with the lowest possible sum (placed in the 4th column) of the 3 numbers.

One possible combination would be:
Item1 Item2 Item100 170

etc...

I need to list all possible combinations, without re-using an element from a previous (lower sum) combination that matched the criteria. Any ideas?

Thanks for the reply...I didn't do a great job of explaining exactly what I need and I had to add another variable to the equation as well. Hopefully the attached file will help clarify (cell coloring for illustrative purposes only). Once sets are made, I need to remove the items used in sets from the input table. Any left over items remain in the input table and each day, more items are added and the matching process begins again. The way I made sets in the attached spreadsheet is by sorting the input table in ascending order by length and making the first possible sets meeting the criteria. I don't know if this is the best way to determine a set, which is why you'd have to make all posible permutations which match the criteria, then sort the matched sets in ascending "waste" order, making sure an item in a lower row doesn't appear in a set above it.

The number of different selections of 3 elements from 100 elements is
100*99*98/(3*2*1) = (approx) 1,000,000 / 6 = 166,000. This makes an exact solution expensive in time and storage space.

The usual practical approach is the Greedy algorithm. You start with the biggest item that will fit your conditions, then add the next biggest, and so on. Then, you alter the search to make reasonable "mistakes", taking some choices that are not biggest, and see if you happen on a better fit. You look at as many other choices as you can within your time constraints, and usually that is enough for practical purposes.

Thanks for the reply...instead of considering all possible combinations of matched sets, I guess we're looking at some kind of VB script that:

1. Starts at the first row of the sorted input table and stores the flow and length values in temporary variables
2. Proceeds to the next row of the sorted table and stores the flow and length values in a second set of variables.
3. Proceeds to the next row and stores a third set of variables.
4. Performs a calculation on the stored variables to determine if the sum of the flows falls within the necessary range.
5. If so, populate the first row in the output table with the results and delete the three rows from the input table and resort.
6. If not, replace the third input row with the next available input row and recalculate. Continue looping through the subsequent rows until a set can be made. This might require nested loops because if no acceptable third variable makes a matched set, the second and then the first input rows would have to be increase by 1 (while also making sure that row is not already being used in the variable set) each time the loop runs without a successful "hit" meeting the conditions.
7. Repeat until no additional matched sets are found.

Would this yield the least waste? If so, what would the script look like? If not, how could it be optimized?

The approach you outlined is correct, it is the straightforward Greedy algorithm without "side searches" for other possible matches. Essentially, include the biggest flow that you can at each point, and take the first result that matches the overall conditions.

It is not optimal, because there can be other combinations in the data that would be better. For example, if the goal is to choose amounts that add closest to 100 without going over, consider this data: 50, 40, 25, 25.

The Greedy algorith would pick 50 + 40 and stop at a total of 90. It can't fit in a 25, so it stops. Obviously, if it skipped 40 (violating Greedy) it would end up with 50 + 25 + 25 = 100, a perfect fit.

So, Greedy is a good first algorithm, and adding "side searches" that explore other combinations can give a better result. Unfortunately, there is no way of being "perfect" without examining all possibilities, and there are too many of them.

I don't have such VBA code, so you would need to look around or write your own version.

I have attached a worksheet that works on a simpler problem that tries to fit quantities into bins. I shows a worksheet approach, and may give you some ideas. This doesn't solve your problem, but I did have it lying around.

I was talking to a friend today and he said there may be an easier way to do this. You make a table on one sheet that takes your input data and you make a second table on another sheet that serves as your output "sets" table. Since we're making combined sets of 3 items from the data input table, the output table will always be a maximum of 1/3 the number of rows of the input table. If your starting list is 100 items, the maximum number of acceptable unique sets you can end up with is 33.

The number of possible iterations of 100 items being made into sets of 3 is (100*99*98)/6 or 161,700 but you don't want to create a table with that many rows, so you limit the output table size to just what you need and overwrite existing values if a better set is found than one already in the table (as you iterate through the various permutations).

A nested loop could be used to create possible combinations in memory processing rows in the input table, simplified like this:

For x = 1 to 100
For y = x+1 to 99
For z = y+1 to 98

Perform analysis on possible set and see if it meets the criteria
Check output table to see if any items from current set are already in the table
If so, overwrite the output table row with new set values if waste value is smaller
If not, write set data to next available row in output table

Next z
Next y
Next x

Anyone think their VBA is good enough to perform this type of function?