Minimum permutation in sublinear time?

11 points · submitted Dec 2019 by u/Noctune

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 · 84% upvoted · other discussions

comments

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.

permalink

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?

permalink

Noctune [OP] 1 points · Dec 2019

Oh I thought by "the list" you meant the query list (query in the code above) that you then applied the permutations to (permutations in the code above).

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)?

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. Then n = k!. If we assume such a datastructure described above exists, then the time to find the minimum permutation would be O(lg n) = O(lg k!) = O(k lg k) (by Stirlings approximation). I.e. equivalent to sorting a list of length k. So it makes sense wrt. sorting in the n = k! case, so it might also "make sense" in the case of n < k!.

Of course that does not necessarily mean that it generalizes to a subset of all permutations. But it might.

permalink

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.

permalink

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

permalink

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.

permalink

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.

permalink

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.

permalink

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.

permalink