Computing counts of combinations (?) 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&gt; val items = List('A', 'B', 'C')
items: List[Char] = List(A, B, C)

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

scala&gt; 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&gt; combos.map(s =&gt; s -&gt; people.count(p =&gt; s.subsetOf(p.toSet))).toMap
res15: scala.collection.immutable.Map[scala.collection.immutable.Set[Char],Int] = Map(Set(A, C) -&gt; 0, Set(B) -&gt; 2, Set(A, B, C) -&gt; 0, Set(A, B) -&gt; 1, Set(A) -&gt; 1, Set(C) -&gt; 1, Set(B, C) -&gt; 1)
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.