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

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.