Thursday, March 23, 2017

Minimum Equivalent

To find equivalence classes of spaces, and of polytopes, it is impractical to try all permutations of a representation to find if it makes one equal to another. Assuming permutations of representations are comparable as greater or lesser, an approach would be to find the permutation that minimizes a representation the most. Then all equivalent representations would minimize to the same member of the equivalence class. To find the minimizing permutation, choose transpositions such that the first transposition chooses which identifier will be the smallest. Of course, multiple transpositions could cause the smallest identifier to be first in the representation. Some transposition sequences would get weeded out only after subsequent transpositions failed to compete with their peers. Weeding out transposition sequence prefixes as unable to recover potential after failing to put the smallest identifiers first in the representation is justified because no subsequent transposition affects the position of lesser identifiers. This algorithm is not O(n), but it is potentially, and I suspect in practice, much better than the O(n!) of the naive approach of trying every permutation. Since I needed to use the same algorithm for both spaces and polytopes, I created a Haskell class of permutation types. Each permutation type must implement refine and compare functions. A refine function returns a list of permutations, each with one more transposition than the given permutation. A compare function takes two partial permutations and compares their application to a representation. To accomplish the compare function, each type in the class is actually a wrapper around an original representation and a partial permutation of that representation.

No comments: