Data Visualization: The Freedman–Diaconis rule

Choose the bin width from the spread of the middle half of the data, so that outliers do not decide it.

What to build

A program that bins data with the Freedman–Diaconis rule, falling back to Sturges' rule when the IQR is 0.

Requirements

  • Q1 and Q3 use linear interpolation: for p = 0.25 and 0.75, take position (n − 1) × p in the sorted values, and interpolate between the values on either side. IQR = Q3 − Q1.
  • If IQR > 0: width = 2 × IQR / n^(1/3), k = ceil((max − min) / width); print IQR = I, width = W, bins = K. Otherwise use Sturges' rule (k = ceil(log2 n) + 1, width = (max − min) / k) and print IQR = 0.00, using Sturges: width = W, bins = K. I and W have two decimals.
  • Print each bin as LO - HI | BAR COUNT (two decimals, # bars, bins starting at the minimum, the last one also holding the maximum), then Sturges would use S bins.

Input

One line of numbers separated by spaces.

Output

The header line, k bin lines, and the comparison line.

Constraints

2 to 1000 values, not all equal.

Example

Input:

1 2 3 4 5 6 7 8

Output:

IQR = 3.50, width = 3.50, bins = 2
1.00 - 4.50 | #### 4
4.50 - 8.00 | #### 4
Sturges would use 4 bins

Why it works

The IQR measures the spread of the middle half of the data and ignores the extremes, so the bin width follows the bulk of the data instead of being stretched by a few outliers.

Examples

Example 1 · Input
1 2 3 4 5 6 7 8
Expected output
IQR = 3.50, width = 3.50, bins = 2
1.00 - 4.50 | #### 4
4.50 - 8.00 | #### 4
Sturges would use 4 bins
Example 2 · Input
1 1 1 1 5
Expected output
IQR = 0.00, using Sturges: width = 1.00, bins = 4
1.00 - 2.00 | #### 4
2.00 - 3.00 |  0
3.00 - 4.00 |  0
4.00 - 5.00 | # 1
Sturges would use 4 bins

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Quartiles by linear interpolation: the p quartile is at position (n − 1) × p in the sorted data, between the two nearest values.

Hint 2

k = ceil((max − min) / width); the bin index is min(int((v − min) / width), k − 1).

Solution

Show one correct solution (try it yourself first)
import math

values = sorted(float(v) for v in input().split())
n = len(values)
lo, hi = values[0], values[-1]


def quantile(p):
    pos = (n - 1) * p
    i = int(pos)
    frac = pos - i
    if i + 1 < n:
        return values[i] + frac * (values[i + 1] - values[i])
    return values[i]


iqr = quantile(0.75) - quantile(0.25)
sturges = math.ceil(math.log2(n)) + 1
if iqr > 0:
    width = 2 * iqr / n ** (1 / 3)
    k = math.ceil((hi - lo) / width)
    print(f"IQR = {iqr:.2f}, width = {width:.2f}, bins = {k}")
else:
    k = sturges
    width = (hi - lo) / k
    print(f"IQR = 0.00, using Sturges: width = {width:.2f}, bins = {k}")
counts = [0] * k
for v in values:
    counts[min(int((v - lo) / width), k - 1)] += 1
for i, c in enumerate(counts):
    a = lo + i * width
    print(f"{a:.2f} - {a + width:.2f} | {'#' * c} {c}")
print(f"Sturges would use {sturges} bins")

Lesson: Histograms and binning →