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?
19 comments · 81% upvoted · other discussions
Assign to every permutation its lexicographical index.You can find, for any permutation, its lexicographical index in linear time.Find for every permutation its symmetrical representative's index, and create a map (permutation index) -> (representative index)
Now given a permutation, you can find its representative in linear time on the permutation size. Find its lexicographical index and query the permutation map (which can be an array or a hash map).
Given the permutation's lexicographical index, you can reconstruct the permutation in linear time. If you want some pseudocode feel free to ask, but you can find it easly on SO
Noctune [OP] 2 points · Dec 2019
But the input when querying is a list, not a permutation. It may contain duplicate elements.
marcorubini301 2 points · Dec 2019
So just to be clear, the set of symmetries are permutations that reorder the input array. Given an input array that represents the game state, you want to find its lexicographical smallest symmetry.
Noctune [OP] 2 points · Dec 2019
Exactly. Am I correct in what you wrote above assumes a permutation as input array?
marcorubini301 3 points · Dec 2019
Yes, i thought the game state was a permutation, now the problem is clear to me.If the query is any array of integers, you can build an n-ary tree on the symmetries as suggested, and greedily descend until you arrive at a leaf which represents the target lexicographical smallest symmetry. It takes linear time in the size of the input array, and you can't do better than this.
If the input array has repetitions, than you can't greedily descend and you need to check different subtrees. You should descend with a bfs keeping track of the best symmetry prefix so far. In the worst case, all symmetries are equivalent and you go back to your original's algorithm complexity.