Minimum permutation in sublinear time?

I'm trying to solve a game with quite a few symmetries (like in tic-tac-toe where turning the board does not change the situation for you or the opponent). To find some canonical representation of a game state, I go through all the symmetries (which are just permutations) and pick the lexicographically smallest one. This is O(n) in the number of symmetries, but I wonder if there is a sublinear solution by somehow preprocessing the permutations.

Note that I consider the length of the list fixed and the number of permutations to be n, I.e. I only want to make it sublinear wrt. the number of permutations.

To demonstrate the data structure I am looking for, here is a simple O(n) solution in Python:

``` import numpy as np

class MinPermutationIndex: def init(self, permutations): self.permutations = np.asarray(permutations)

# Can this method be implemented in sublinear time wrt. the number of permutations in the index?:
def min_permutation(self, query):
    permuted = np.asarray(query)[self.permutations]

    # actually O(n lg n) but can be implemented in O(n)
    return permuted[np.lexsort(permuted)[0]]

permutations = MinPermutationIndex([ [2, 0, 1], [2, 1, 0], [0, 1, 2], [0, 2, 1], ])

assert np.all(permutations.min_permutation([5, 2, 1]) == [1, 2, 5]) assert np.all(permutations.min_permutation([1, 0, 0]) == [0, 0, 1]) ```

So do you have any articles or insights that might be useful here?