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

``````(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 women, 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 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 women, three men, 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 women seated together.  And when I started to program, I stayed with that simple view: men and women.

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 about half a percent 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 really 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.

Cover photo by JC Dela Cuesta