1
$\begingroup$

This is a simplification of a real world problem and only a small piece at that.

Example sets are

----------------------       ------------------------------------  
| Set1 | Set2 | Set3 |  OR   | Set1 | Set2 | Set3 | Set4 | Set5 |
|--------------------|       |--------------------|--------------
| 1    | 10   | 40   |       | 1    | 1    | 1    | 1    | 1    |
| 2    | 12   | 45   |       | 2    | 2    | 2    | 2    | 2    |
| 3    | 13   | 51   |       | 3    | 3    | 3    | 3    | 3    |
| 4    | 20   | 61   |       | 4    | 4    | 4    | 4    | 4    |
| 5    | 25   | 76   |       | 5    | 5    | 5    | 5    | 5    |
|      | 31   | 78   |       ------------------------------------
|      |      | 81   |
----------------------       

Real world constraints are

  • Up to 12 sets
  • N numbers in each set
  • Only care about distinct combinations - (112), (211) and (121) are considered the same.

Example with desired result

----------------------
| Set1 | Set2 | Set3 |
|---------------------
| 1    | 1    | 1    |
| 2    | 2    | 2    |
| 3    | 3    | 3    |
----------------------
Results: [1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]

Generally real world examples tend to either be like the first example where there are a variable number in each set and they are different in each set, or like the second where there are the same items in each set. However there are no hard and fast rules.

A real world example of the latter is 10 sets with 40 values in each. To naively iterate that example would be $1x10^{16}$ iterations.

Are there any optimal algorithms I can implement to find distinct combinations? I am hoping that there is something clever that can be done when there are the same items in different sets, somehow excluding them once certain conditions are met, but i have failed to think of or find one.

$\endgroup$
  • $\begingroup$ Confusing why no [1,2,1] ? $\endgroup$ – paparazzo Jul 14 '17 at 17:47
  • $\begingroup$ So two sets $s_1$ and $s_2$ are equal if $\text{sorted}(s_1) = \text{sorted}(s_2)$? $\endgroup$ – Pål GD Jul 14 '17 at 18:12
  • $\begingroup$ @Paparazzi [1,1,2] is the same as [1,2,1] $\endgroup$ – Robert Snipe Jul 16 '17 at 7:27
  • $\begingroup$ You're right, that formula was wrong. I think the correct formula for $n$ identical sets of $k$ elements is ${n+k-1} \choose k$, so in the case of 40 sets of 10 elements, the number of combinations would be 8,217,822,536, which is probably practical. (If the sets are not identical, the count climbs rapidly.) If you know the sets to be identical, you can use the algorithm presented by @fade2black, but in the general case I don't believe there is a simple solution. $\endgroup$ – rici Jul 16 '17 at 13:51
  • $\begingroup$ Shame the answer isn't there now for reference. Using that approach you could apply it to any subset of identical numbers and then combine with any remaining unique numbers. It would quite probably be more effort than it was worth. I do't quite get how that formula in your comment gets to that number, though I know that is the right result. I have it as !(n+k-1)/(!(k-1)!n). Your comment answers my question by proving that it would still be a very large number at best so if you make it a full answer I will accept it $\endgroup$ – Robert Snipe Jul 19 '17 at 13:38
-1
$\begingroup$

This may be wrong
I don't follow the multiple set of the set input part of question

Have a loop for each N

Assume N = 3
L is length of array A

for(i = 0; i < L-2; i++) 
    for(j = i + 1; j < L-1; j++) 
        for(k = j + 1; k < L; k++)
            A[i], A[j], A[k]

I write poker software and this matches the number of combinations

$\endgroup$
  • $\begingroup$ This only works if all the input sets are the same. The question wants a solution that works even if that is not the case. $\endgroup$ – D.W. Jul 14 '17 at 19:31
  • $\begingroup$ @D.W. I stated I don't follow the multiple set of the set input. $\endgroup$ – paparazzo Jul 14 '17 at 21:26
  • $\begingroup$ The welcome committee is still active $\endgroup$ – paparazzo Jul 16 '17 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.