0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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, 2017 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, 2017 at 11:24
  • $\begingroup$ Details in the solution for it would be appreciated, thanks $\endgroup$
    – Berry
    Jun 27, 2017 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, 2017 at 5:11

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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