A café keeps a daily log as a table of columns, for example {"cups": [...], "temp": [...], "rain_mm": [...]}, where position i of every column belongs to day i. The owner wants to know which column moves most closely in a straight-line way with the number of hot chocolates sold.
Write strongest_links(table, target) that returns a list of pairs (name, r), one for every column except target, where r is the correlation coefficient between that column and the target column:
r = cov(x, y) / (sd(x) * sd(y))
(the covariance and the two standard deviations all divide by n, or all by n - 1; the result is the same). Sort the pairs by abs(r) from strongest to weakest, and pairs with the same abs(r) by name. When a column, or the target itself, has all its values equal, its r is None; such pairs come after all the others, sorted by name.
A strong negative link counts as strong: -0.9 ranks before 0.5.
The setup provides cafe_log(n, seed), which returns a random table with the columns "cups", "temp", "rain_mm", "weekday" and "price" for n days.
Examples
Input: table = {"cups": [30, 22, 18, 10], "temp": [2, 6, 9, 15],
"open_h": [8, 8, 8, 8], "staff": [2, 3, 2, 3]},
target = "cups"
Output: [("temp", -0.9939990885479664), ("staff", -0.5547001962252291), ("open_h", None)]
Explanation: colder days sell more cups, almost perfectly on a straight line, so r is
close to -1. The opening hours never change, so their correlation is undefined.
Constraints
- 2 to 10 columns, each with the same length between
2and20000 targetis one of the column names- floats are compared with a tolerance of
1e-6; two values ofabs(r)count as equal when they differ by less than1e-12
Goals
- Compute Pearson's correlation coefficient of two paired lists
- Rank several columns by the strength of their linear link with a target
- Handle a column with no spread, whose correlation is undefined