A receipt is an array of products. I have an array of receipts.

I need to generate a report in where I can find the products often bought together.

For instance, for a single receipt where the products bought are [A, A, B, B, B, C], a report would look like

Pair - count
A&B - 2
A&A - 1
B&B - 1
A&C - 1
B&C - 1

Notice that pair B&A is no longer counted because this is the same as A&B, and similar occurrences. It also has to be sorted by count, decreasing. Also notice that this is just from one receipt rather than multiple, which is what is required.

I also need the algorithm to scale to triples and quadruples, not just pairs.

How would I create an algorithm like this?

There are no set time efficiency constraints. In fact, a more readable solution is preferred over more efficient solutions although efficiency is also appreciated. A python solution is also appreciated, but any language or pseudocode will do.

  • $\begingroup$ If time is not an issue, why not use the naive algorithm ($n^k$ $k$-tuples of $n$ products)? That said, you seem to be looking or some sort of correlation, which is probably standard in data mining and/or machine learning. I expect there to be smarter methods. $\endgroup$ – Raphael Jun 27 '17 at 6:13
  • $\begingroup$ I don't quite understand what you're trying to accomplish, but it looks like a pretty standard programming exercise, which you don't really need us for. Use hash tables, count stuff, and sort the results. $\endgroup$ – Yuval Filmus Jun 27 '17 at 11:24
  • $\begingroup$ Details in the solution for it would be appreciated, thanks $\endgroup$ – Berry Jun 27 '17 at 11:48
  • $\begingroup$ docs.python.org/2/library/itertools.html Use the permutation function and just set the length you want. $\endgroup$ – Cole Jun 29 '17 at 5:11

This is the itemset mining problem. Use any standard algorithm for that problem. Follow the links to learn more about standard algorithms for that task.

| cite | improve this answer | |

Your Answer

