# 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> 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)

• 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. Aug 28, 2016 at 10:17
• "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? Aug 28, 2016 at 10:19
• 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. Aug 28, 2016 at 10:21