Given a permutation of $1,2,3,\dots,n$, with consecutive elements $a,b,c$ (in that order), we may perform either of the [i]moves[/i]:
[list]
[*] If $a$ is the median of $a$, $b$, and $c$, we may replace $a,b,c$ with $b,c,a$ (in that order)
[*] If $c$ is the median of $a$, $b$, and $c$, we may replace $a,b,c$ with $c,a,b$ (in that order)
[/list]
What is the least number of sets in a partition of all $n!$ permutations, such that any two permutations in the same set are obtainable from each other by a sequence of moves?

[i]Proposed by Milan Haiman[/i]
To solve this problem, we need to determine the least number of sets in a partition of all \( n! \) permutations such that any two permutations in the same set are obtainable from each other by a sequence of the given moves. Let's break down the solution step by step.

1. **Define Inversions:**
   In a permutation \(\sigma\), a pair \((i, j)\) is called an inversion if \(i < j\) and \(\sigma(i) > \sigma(j)\). This is a key concept because the given moves do not change the total number of inversions in the permutation.

2. **Invariance of Inversions:**
   The moves described in the problem do not change the total number of inversions in the permutation. This is because:
   - If \(a\) is the median of \(a, b, c\), then \(a < b < c\) or \(c < b < a\). Replacing \(a, b, c\) with \(b, c, a\) or \(c, a, b\) does not change the relative order of \(a, b, c\) in terms of inversions.
   - Similarly, if \(c\) is the median, the move does not change the relative order of \(a, b, c\) in terms of inversions.

3. **Invariance of Ordering Between 1 and n:**
   The ordering between 1 and \(n\) cannot be changed by the given moves. This is because:
   - If \(1\) is before \(n\) in the permutation, it will remain before \(n\) after any sequence of moves.
   - If \(1\) is after \(n\), it will remain after \(n\) after any sequence of moves.

4. **Counting Possible Inversions:**
   For a permutation \(\sigma\) where \(1\) is before \(n\), the number of inversions is a number between \(0\) and \(\frac{(n-1)(n-2)}{2}\). This is because the other \(n-2\) numbers can have at most \(\frac{(n-2)(n-3)}{2}\) inversions among themselves, and each of them can build \(1\) or \(0\) inversion with \(1\) and \(n\).

   Similarly, if \(1\) is after \(n\), the number of inversions is between \(n-1\) and \(\frac{n(n-1)}{2}\).

5. **Number of Classes:**
   In both cases, there exist \(\frac{(n-1)(n-2)}{2} + 1\) choices for the number of inversions. Therefore, the number of such classes is at least:
   \[
   2 \left( \frac{(n-1)(n-2)}{2} + 1 \right) = (n-1)(n-2) + 2
   \]

6. **Conclusion:**
   The least number of sets in a partition of all \(n!\) permutations, such that any two permutations in the same set are obtainable from each other by a sequence of moves, is:
   \[
   n^2 - 3n + 4
   \]

The final answer is \(\boxed{n^2 - 3n + 4}\).