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
It seems like your problem is similar to finding the minimum of a list. Your list values are sequences of integer values and one list value is smaller than another if it contains an element smaller than an element in the other at the same position (given that elements at earlier positions are identical.) If the largest integer present in any sequence is MaxValue, there's a list of base MaxValue numbers that you want to find the minimum of. Without some additional guaranteed structure to the problem instance, sublinear seems inaccessible. To find a minimum, you need to examine every element at least once. Any preprocessing that you do needs to systematically ignore portions of the input in order to avoid a worst case linear running time. You would have to resort to a randomized algorithm that may be incorrect, but iterating it reduces the probability of error.
Noctune [OP] 1 points · Dec 2019
I'm looking for sublinear in the number of permutations, not sublinear in the length of the list. I agree that sublinear in the length of the list does seem inacessible.
Edit: I've edited the original post to be more clear.
Barelytoned 2 points · Dec 2019
I'm not sure that I understand the difference between the number of permutations and the length of the list. I'm assuming the list is a data structure that contains all permutations of a sequence. Are there fewer permutations under consideration (the 'symmetries' you reference)? Are you trying to find something sublinear specifically because you know you can ignore a portion of the list that's a constant factor of the size of the list?
EDIT: Is this where my misunderstanding is? After re-reading the original post, is it true that: The list contains E elements that can be expressed in E! different permutations, so you're looking for a sublinear algorithm for finding the minimum of E! permutations?
Noctune [OP] 1 points · Dec 2019
Oh I thought by "the list" you meant the query list (
queryin the code above) that you then applied the permutations to (permutationsin the code above).It does not necessarily contain all permutations. If it did contain all permutations, this would actually just be equivalent to sorting the elements in the query list.
I think it might be possible to structure the permutations in a tree in such a way that it only requires
O(lg n)time to find the minimum permutation. The reason I think such a datastructure might exist is as follows:Consider the case where the permutation list does contain all permutations of length
k. Thenn = k!. If we assume such a datastructure described above exists, then the time to find the minimum permutation would beO(lg n) = O(lg k!) = O(k lg k)(by Stirlings approximation). I.e. equivalent to sorting a list of lengthk. So it makes sense wrt. sorting in then = k!case, so it might also "make sense" in the case ofn < k!.Of course that does not necessarily mean that it generalizes to a subset of all permutations. But it might.
Barelytoned 2 points · Dec 2019
My first thought is: Building the n-ary tree to store the permutations is relatively expensive to the O(logn) you're looking for (maybe linear and probably worse in the size of the list with access to a list of valid permutations), can you build it while also generating/evaluating the permutations you know are present in your problem (so it only affects the constant or gets absorbed by a worse efficiency elsewhere?) If you have some list of 'valid' permutations present in your problem (that has fewer than all possible permutations), the tree has an empty root and children corresponding to values that appear as the first element of some valid permutation. Subpermutations (permutations where the first i positions are fixed) are children of nodes at depth i+1.
I agree that with access to a n-ary tree data structure, finding the minimum can be done in O(log(n)) comparisons rather than the usual O(nlog(n)).
Noctune [OP] 0 points · Dec 2019
I only care about the cost of querying, so building a data structure can be anywhere as expensive as it has to be (within reason of course).
I don't think the prefix-tree idea works since there might be duplicate elements in the query list. The algorithm would have to go down multiple branches. Pathological cases like a list of identical values ends up being O(n).
Barelytoned 2 points · Dec 2019
I'm not sure I understand why duplicates would interfere with building the tree. If I'm given the list [0, 0, 0, 1], the tree is just more sparse than the list [1,2,3,4] because there are fewer unique values in the list. I'm having trouble constructing an example where you'd have to explore multiple branches due to duplicate elements. By definition, if I'm at node n in the tree examining the children for the smallest value, the smallest value is present exactly once. It doesn't matter how many times the smallest value is present in the original list.
Noctune [OP] 1 points · Dec 2019
The duplicates does not interfere with building the tree, but when querying it.
But I am not building a tree of the applied permutations - doing that would be no better than linear scanning through the permutations. The tree would have to be built on the indices of the permutations, in which case different indices may result in the same value due to duplicates in the query list.
Lets say we have the permutations
[[0, 1, 2], [1, 2, 0]]. This would result in a tree likeRoot - 0 - 1 - 2 - 1 - 2 - 0But when given the query list
[0, 0, 1]we have to decide at the root whether to go down the left or the right branch and the only indices we have to compare are 0 and 1, the values of which both are 0.Unless I have misunderstood how you meant to build the tree, I cannot see any way to avoid having to descend multiple branches.
deong 1 points · Dec 2019
If the list of permutations is already sorted, then you can just select the first item in constant time and you don't need to solve anything. If it’s not already sorted, it takes O(n log n) time to put all elements in the search tree. You only need the minimum, which you can do in O(n) time by just scanning the list.
It is not possible to find the smallest element of an arbitrary unsorted collection in sublinear time, full stop. The only way this can work is if your list of permutations has some type of structure you can exploit. As a trivial example, if your procedure for generating each permutation always puts the one with the smallest score at the head of the list, then obviously you can just stop after one item and you're O(1). There has to be something about your specific list like that to rely on. Otherwise, scanning the list is the best you can do.
Noctune [OP] 1 points · Dec 2019
The list of permutation is constant and can be sorted, but sorting this does not help me directly since I am interested in the lexicographically minimum permutation of the game state (i.e. the permutations have to be applied to the game state).
But this does not mean there is no structure for us to exploit. For example if the query list is a permutation then we can build such an index (as demonstrated by other comments on this post).
deong 1 points · Dec 2019
I'm not seeing how it matters. Forget the fact that it's permutations. You have n descriptions of a game state, each of which has some value function applied to it. You need to find the one of those n that has the minimum value, right?
You can't do that better than linear time unless you can "cheat" in some way by taking advantage of the fact that the arrangement of items in the list has some pattern that lets you reliably skip looking at some of the inputs. That is 100% a property of the way you build the list. What you've given us is basically, "I have a list". If that's all we have to go on, scanning the list in linear time is provably optimal.
Noctune [OP] 1 points · Dec 2019
Sure, but there are exactly properties of permutations that can be exploited. The permutations are reorderings of the same list, so transitivity of the order of the elements in the list holds. This could likely be used to skip permutations.
For example, sorting a list of length k is equivalent to picking the lex. minimum permutation of all k! possible permutations. Similarly, a partial sorting networks could work for at least some sets of permutations. I don't know whether there are some properties for arbitrary sets of permutations that can be exploited, which is why I am asking this question.
deong 1 points · Dec 2019
I may not have understood the problem correctly. Is it the case that you have n permutations of the same game state, and so the value of each is the same? And the problem is just standardizing the way you represent that for the purposes of comparing it to others?
I was thinking of this as each permutation being a separate state and you needed the one with the best value function. In which case, pretty trivially you need to scan the whole list.
Noctune [OP] 1 points · Dec 2019
Yeah, I think there is some confusion in what you and I mean by "permutation". What I refer to a permutation is a list of indices to reorder another list of same length (eg. [0, 2, 1]). What I think you and others refer to as a permutation is the applied reordering of some game state (eg. [5, 1, 2] permuted by the prev. reordering results in the permutation [5, 2, 1]).
They are both technically permutations - the first one being a permutation of the 1,2..n, and the second being a permutation of the game state. I can't really find a succinct word to distinguish the two.
So I have n such "blueprint permutations" that when applied to the game state return a permutation of the game state. And I then want to find the lex. minimum permutation found by applying these n permutations to the game state.