2
$\begingroup$

I'm not sure what terminology to use. Here is some input:

John  has items: A B D
Peter has items: A C D

And I want to produce such a table, that would count the # of people having these items (0-count is not required to be outputted):

A     2
B     1
C     1
D     1
A,B   1
A,C   1
A,D   1
A,B,D 1
A,C,D 1

What's the name of such a table and what sort of efficient algorithm could I use to produce it?

Functional programming style more preferable. An Excel solution would be great though I'm not sure it's doable.

It would be used to determine if there are any correlations.

Thank you.

PS here is a rudimentary example solution in Scala which isn't efficient:

scala> val items = List('A', 'B', 'C')
items: List[Char] = List(A, B, C)

scala> val people = List(List('A', 'B'), List('B', 'C'))
people: List[List[Char]] = List(List(A, B), List(B, C))

scala> val combos = (1 to items.size).view.map(items.combinations(_).map(_.toSet).toSet).flatten
combos: scala.collection.SeqView[scala.collection.immutable.Set[scala.collection.immutable.Set[Char]],Seq[_]]#Transformed[scala.collection.immutable.Set[Char]] = SeqViewMN(...)

scala> combos.map(s => s -> people.count(p => s.subsetOf(p.toSet))).toMap
res15: scala.collection.immutable.Map[scala.collection.immutable.Set[Char],Int] = Map(Set(A, C) -> 0, Set(B) -> 2, Set(A, B, C) -> 0, Set(A, B) -> 1, Set(A) -> 1, Set(C) -> 1, Set(B, C) -> 1)
$\endgroup$
3
  • $\begingroup$ What does "efficient" mean for you? The table will be exponentially large in the number of items. (Shouldn't D and A,D have count 2? Why are there no rows B,C, B,D and C,D?) Please give a precise, general specification for the output; a single example is usually not sufficient to remove all ambiguity. $\endgroup$
    – Raphael
    Aug 28, 2016 at 10:17
  • $\begingroup$ "It would be used to determine if there are any correlations." -- please explain. What kind of correlations? Why do you think you need a full subset-count for this purpose? $\endgroup$
    – Raphael
    Aug 28, 2016 at 10:19
  • 1
    $\begingroup$ Idea: Represent sets as bit vectors. Then, $A \subseteq B$ if and only if $b_A \land b_b = b_A$. That won't give you a polynomial algorithm (since you'd have to check all $2^n$ subsets of your $n$-item set) but the individual checks are fast. $\endgroup$
    – Raphael
    Aug 28, 2016 at 10:21

1 Answer 1

3
$\begingroup$

These combinations of items are sometimes called itemsets. There are algorithms for finding itemsets that are especially common in a database; see association rule learning.

In general there is no efficient algorithm for producing such a table, as the size of the table can be exponentially large in the size of the input. Consequently any algorithm will take exponential time on at least some inputs (i.e., will be extremely slow on at least some inputs). You might want to consider what you plan to do with the table and whether there's a way to achieve your ultimate goal, without building the table explicitly; that might turn out to be a better approach.

$\endgroup$

Your Answer

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

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