# Table Gender Seating Probabilities

## Exploring the likelihoods of different patterns of table seating, with Clojure.

##
March 30, 2018

The other morning, while walking with my friend Bec, she remarked observing meeting attendees self-sorting, by gender, on sides of a conference table. She wondered aloud as to the likelihood that it was just random chance.

As engineers are wont, we started to talk through calculating probabilities of different arrangements of people around a table. Having recently started to learn Clojure I’m always on the lookout for new challenges so I tucked it away as something to think about on the walk home.

The first algorithm that came to mind was:

- Generate all the permutations of seating arrangements for attendees
- For each permutation, look at one side of the table
- Record the number of seats,
`n`

, filled by gender`g`

The probability of `n`

persons of gender `g`

, sitting on one side of
the table together is the number of permutations recorded with `n`

persons of gender `g`

, over the total number of permutations.

…something like that seemed pretty reasonable as a starting point.

# The Final Code

From jcorrado/experiments on GitHub.

```
(ns clojure-experiments.table-seating-probability
(:require [clojure.spec.alpha :as s]
[clojure.math.combinatorics :as combo]))
(defn calc-side-permutations
[coll]
{:pre [(s/valid? even? (count coll))]}
(map (partial take (/ (count coll) 2))
(combo/permutations coll)))
(defn calc-probabilities
[id coll]
(let [perms (calc-side-permutations coll)
total (count perms)]
(->>
(frequencies (map (fn [p]
(get (frequencies p) id)) perms))
(reduce-kv (fn [m n cnt]
(assoc m n (float (/ cnt total))))
{}))))
(defn report-probabilities
[m]
(doseq [n (-> (keys m) sort reverse)]
(println (format "%.3f probability of %d on one side" (get m n) n))))
```

## An Example Run

Here we’re looking at possible groupings of three females, in a meeting of seven attendees, around an eight person table.

We have one function, `calc-probabilities`

to generate and process
permutations of seating and another, `report-probabilities`

, to format
and generate our output.

```
(-> (calc-probabilities \f (concat (repeat 3 \f)
(repeat 3 \m)
(repeat 1 \x)
(repeat 1 nil)))
report-probabilities)
;; 0.071 probability of null on one side
;; 0.429 probability of 1 on one side
;; 0.429 probability of 2 on one side
;; 0.071 probability of 3 on one side
```

# Solution Walk Through

## Representing Our Input

We start off with a list of chars representing meeting attendees. If
there are fewer participants than seats, we pad with `nil`

.

Here we have three *females*, three *males*, one *non-binary*, and one
*empty* seat.

```
(concat (repeat 3 \f)
(repeat 3 \m)
(repeat 1 \x)
(repeat 1 nil))
;; => (\f \f \f \m \m \m \x nil)
```

A note on *non-binary*

When I first started thinking about this problem, Bec and I were talking about an observed group of females seated together. And when I started to program, I stayed with that simple view: men and women, male and female.

But as I thought about it more; thought about all the people I’ve
known, and did the tiniest bit of research, I realized this wasn’t a
complete picture. By some accounts, ~0.6% of people identify as
*non-binary*. That’s a lot of people I’d rather not exclude.

## Permutation Calculation

The first thing to do is calculate all the **distinct** permutations
of the input list. I’m using
`permutations`

,
from
`math.combinatorics`

hereafter referenced as `combo`

.

The detail of *distinct* is important. Strictly speaking, the set of
permutations for a given input collection does not include duplicate
permutations of elements.

This is probably what you expect:

```
(combo/permutations [\f \m \x])
;; => ((\f \m \x)
;; (\f \x \m)
;; (\m \f \x)
;; (\m \x \f)
;; (\x \f \m)
;; (\x \m \f))
```

But consider an input collection with repeated elements. Here we only have three returned permutations.

```
(combo/permutations [\f \f \m])
;; => ((\f \f \m)
;; (\f \m \f)
;; (\m \f \f))
```

The duplicate permutations were not returned. This makes sense to me: we’re examining the groupings of people by their gender identity, not the unique people, themselves.

`calc-side-permutations`

takes our initial input collection and
returns a list of distinct permutations.

Our algorithm depends on the table having an even number of seats, so we attach a validating spec.

```
(defn calc-side-permutations
[coll]
{:pre [(s/valid? even? (count coll))]}
(map (partial take (/ (count coll) 2))
(combo/permutations coll)))
```

Order matters in permutations: `\f \f \m`

is different than `\m \f \f`

so we have both in our generated list. We only care about one side of
the table so we grab the first half of each of our permutations and
halve the work to do later. This is actually the only clever
optimization in the algorithm.

“The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.”

– Donald Knuth

Here’s an example: the first two elements in the 12 distinct
permutations of `\f \f \m nil`

.

```
(calc-side-permutations [\f \f \m nil])
;; => ((\f \f)
;; (\f \f)
;; (\f \m)
;; (\f \m)
;; (\f nil)
;; (\f nil)
;; (\m \f)
;; (\m \f)
;; (\m nil)
;; (nil \f)
;; (nil \f)
;; (nil \m))
```

## Probability Calculation

Let’s take apart `calc-probabilities`

a bit and explore some of
Clojure’s interesting constructs.

```
(defn calc-probabilities
[id coll]
(let [perms (calc-side-permutations coll)
total (count perms)]
(->>
(frequencies (map (fn [p]
(get (frequencies p) id)) perms))
(reduce-kv (fn [m n cnt]
(assoc m n (float (/ cnt total))))
{}))))
```

As setup, we calculate our permutations, described above, and save a count for future stats calculation. Two expressions drive the real work.

Our input set `(\f \f \f \m \m \m \x nil)`

generates 1,120 distinct
permutations (8! = 40,320 before removing dupes).

The first expression - the `frequency`

-`map`

-`frequency`

construct -
maps over each of the 1120 permutations building a hash-map of each id
type, pulls out the value of the type we’re interested in (`id`

, in
this case `\f`

), then builds a frequency map of that list of 1120
counts-per-permutation.

Here we have 80 permutations with 0 (nil) or 3 `\f`

and 480 with 1 or
2.

```
;; id => \f
(frequencies (map (fn [p]
(get (frequencies p) id)) perms))
;; => {3 80, 2 480, 1 480, nil 80}
```

The `->>`

reader macro is some syntactic sugar that passes the
hash-map returned by evaluating the `frequency`

-`map`

-`frequency`

construct (`{3 80, 2 480, 1 480, nil 80}`

) as the final argument to
the next expression (`reduce-kv`

); it helps clarify the code by
avoiding too much nesting.

The second expression - the `reduce-kv`

construct - is used to
calculate our stats. Once we know how many of a given gender are
present on a side, and the total number or permutations, (`total`

), we
can calculate the probability.

```
;; total => 1120
(reduce-kv (fn [m n cnt]
(assoc m n (float (/ cnt total))))
{})
;; => {3 0.071428575,
;; 2 0.42857143,
;; 1 0.42857143,
;; nil 0.071428575}
```

Finally, we format and print our output.

```
(defn report-probabilities
[m]
(doseq [n (-> (keys m) sort reverse)]
(println (format "%.3f probability of %d on one side" (get m n) n))))
;; 0.071 probability of null on one side
;; 0.429 probability of 1 on one side
;; 0.429 probability of 2 on one side
;; 0.071 probability of 3 on one side
```

So there you have it. Some Clojure code, looking at the probability of different patterns of seating, picked apart for the fun of the language.

Thoughts on the underlying algorithm?

Thoughts on the Clojure implementation? There’s an elegance to the language that I find so appealing. Good solutions feel joyous.