CODEWITHSUNDEEP
arrayscombinations
Charles
Charles

Reputation: 4538

Find all "and" combinations from multiple sets

Let's say I have x sets of objects, and each set has a certain number objects. I want create an array which will store all the unique "and" combinations of these objects.

For example, if I have 5 objects in set A, 10 objects in set B, and 8 objects in set C, then I know that there are 5*10*8 = 400 unique ways of picking one object from each set. But I want to actually store these combinations in an array.

So the array would be multidimensional, something like:

{
  { a, a, a }
  { a, a, b }
  { a, a, c }
  ...
  { a, b, a }
  { a, b, b }
  and so on...
}

I need the solution to as efficient as possible, because I am dealing with situations where there are potentially tens of millions of combinations. I am not exactly sure how to begin to approach this problem.

Sorry if it's not clear, but I don't really know what to call what I am trying to achieve, so I am just describing it as best I can. Thank you for any help you can provide.

Edit: Here is some more information about the problem:

The purpose of this problem is that I am going to compute a "score" value from each resulting array. Then, I want to find the top n scores and return them to the user. So actually, I believe that I wouldn't need to have the entire array in memory. I can just iterate through the array, calculate the score, and add it to the returned array if its score is high enough. That way, I only need the top n objects in memory continuously.

I hope this makes things more clear.

Upvotes: 1

Views: 214

Answers (2)

dwanderson
dwanderson

Reputation: 2852

Quick python, probably can't get much more efficient, since you need to iterate at some point...

getItems(A, B, C):
    for a in A:
        for b in B:
            for c in C:
                items = (a, b, c) ## or [a, b, c], as desired
                yield items

Or, if you're familiar with generator expressions:

gen = ((a, b, c) for a in A for b in B for c in C)

Then to use:

for combo in getItems(A, B, C): ## or for combo in gen:
    ## do stuff here

Edit:

def getItems(*allSets):
    if len(allSets) == 0:
        yield []
        return
    thisSet, theRest = allSets[0], allSets[1:]
    for value in thisSet:
        for values in getItems(*theRest):
            yield [value] + values

Upvotes: 1

WingedPanther73
WingedPanther73

Reputation: 84

Do you know the number of sets at design-time? If so, I would do nested for loops. If you don't know the number of sets, then you're potentially do some form of recursion to handle the looping.

With that said, I think what you're doing is, by definition, NOT efficient. Is there a reason you need to store all the possible combinations in memory, rather than generating them as needed on the fly?

Upvotes: 0

Related Questions