Efficient way to get median of all subsets.

Question

Given a finite discrete set $X \subset \mathbb{R}$ with cardinality $k$.

The are $2^k$ subsets. For any given subset, there is a median associated with it (Define the median of $\emptyset$ as 0).

Wondering if there are any smart ways to get the $2^k$ medians.

Answer 1

The possible medians are:

• any of the $k$ values
• (if you define the median of an even-sized set as halfway between the two most central values) any mean of two of the $k$ values
• $0$ for the empty set

That makes $k+{k \choose 2}+1 = \frac12k^2 +\frac12k+1$ potentially distinct values for subset medians and explains how to find them; it may turn out that there are some duplicates.