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?


For 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.

  • $\begingroup$ Welcome to CS.SE! Half-baked idea: For $p$, let $p^{-1}(1)$ denote the index that is sent to the first position (i.e., if $i=p^{-1}(1)$, then $(p\cdot s)_1 = s_1$). Store the elements of $P$ hashed/keyed on the value of $p^{-1}(1)$. Now given $s$, find the indices $i$ such that $p_i$ is minimum, and check only the permutations $p$ such that $p^{-1}(1)=i$. This will often provide a speedup. I suspect you can generalize this by building a tree that first branches on $p^{-1}()$, then on $p^{-1}(2)$, and so on, but I haven't worked out the details. Want to see if that works? $\endgroup$ – D.W. May 7 '17 at 0:38
  • $\begingroup$ Thank you! I am not quite sure that would work since $s$ may have duplicates. Consider $P=\{ (1,2,3,4), (4,3,2,1) \}$ and $v=(0,0,0,1)$. The algorithm would have to take both branches, which is still $O(n)$. $\endgroup$ – Mike Pedersen May 7 '17 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.