1

In a supermarket I selected $30$ products on which we want to run an analysis. I want to see which $12$ of them give me the widest coverage of clients (on a specific date, no time involved).

This means that I have $\displaystyle\frac{30!}{12!(30-12)!} = 86493225$ combinations of products

My dataframe of clients purchases:

Client Product
A Banana
B Apple
B Banana
C Water
...

codewise I could iterate to see the combination of highest client count, I am presenting the same problem as a coding issue here

but do you see a why I could calculate this as a formula, without having to iterate across all combinations?

please note that I do not want to find the combination of $12$ most common products, but the combination that will yield the most clients (possibly the same but not necessarily, as $2$ products not individually common may yield more clients if the $2$ groups don't overlap much).

any thoughts?

thank you

HeroZhang001
  • 2,201
lorenzo
  • 113

1 Answers1

1

You are unfortunately onto the maximum coverage problem, which is NP-hard. In general, there is no easy way to solve this, but since this is itself a common problem, you may be able to find software packages that deal with it specifically.

OTOH, 86 million is really nothing to a computer, as long as your client count isn't in the thousands.

obscurans
  • 3,422
  • hi @obscurans thanks a lot for your reply. now I understand much better the issue, thanks a lot for sharing. I have about 5000 clients, but client count is less of a problem cos I can easily vectorize (with hashes) the count. my code (linked above) runs ~170 iterations per second on my machine, so approx 5-6 days of running, which is acceptable in my case. I was just annoyed by not finding a way to formulate more efficiently the problem. now I see why – lorenzo Mar 10 '23 at 01:05
  • @lorenzo if you're set on finding the absolute optimal solution, there are tons of tiny tricks you can do to optimize. For example, run backtracking - choose at the start whether to include/exclude product 1, then if you do, count and throw away all client records that are already covered before attempting to choose the other 11 slots. This computation can be shared across all possible candidate solutions using product 1 (then 1+2, etc, in a tree). Greedy works here: order the choices that haven't been decided yes/no by number of records that it will immediately cover. – obscurans Mar 10 '23 at 01:19