Given a set of permutations $P$ of size $n$, is it possible to create a data structure that, given a sequence $s$, returns $p \cdot s$ where $p \in P$ such that $p \cdot s$ is canonical wrt. $\{\,q \cdot s \mid q \in P \,\}$ faster than $O(n)$ time?By canonical, I mean for example such that $p \cdot s$ is lexicographically minimal, but any kind of canonical will do.This is easy to do in $O(n)$ time. You just try every single permutation and pick the canonical one (eg. minimum), but is there a faster way?ExampleFor lexicographically minimal canonicalization, if $P=\{ (1,2,3,4),(4,3,2,1),(2,3) \}$ and $v=(0,5,1,0)$, then the result would be $(0,1,5,0)$. This is the application of either the permutation $(4,3,2,1)$ or $(2,3)$, as they are identical in this case.
Canonical permutation faster than O(n)
data structures;permutations