First of all, let's be precise about what exactly we want to do here. Let's say you just figured out a Really Cool Way to compute coordinates for, oh, the omnitruncated E8 polytope, say (I'm just making that up). Now you want to share your great findings with the world. But there's one problem: this thing, it turns out, this monster has like 10000 vertices, and posting 10000 coordinates on your homepage isn't exactly the most readable thing to do. But you know that you can factor these coordinates in nice permutation sets, like Wendy's apacs and epacs operators (aka "all permutations of coordinates, all changes of sign", and "even permutations of coordinates, all changes of sign", respectively). The only problem is, there are too many coordinates to factor by hand (well, there are too many to recognize just by looking, for starters). So how do you go about doing that?

There are probably many solutions to this problem; here's my method.

Partition the vectors into candidate permutations sets

First, you want to group the coordinates in potential permutation sets. For example, if your coordinates include <1,2,3,4,5>, <5,4,3,2,1>, <2,3,4,5,6> and <6,5,4,3,2>, then you'll want to group the first two coordinates into a group, and the second two coordinates into another group, because <5,4,3,2,1> is a permutation of <1,2,3,4,5> but <2,3,4,5,6> is not. How you tell if something belongs in the same group? Easy: just sort the coordinates and compare them. For example, <5,4,3,2,1> sorted becomes <1,2,3,4,5>, so you know it belongs to the same group as <1,2,3,4,5>.

Now, in the real world, things aren't quite this simple. For one thing, polytopes tend to have negative coordinates too (all changes of sign, remember?). So you might have among your coordinates, say, <3,2,-4,1,-5>. You want to put this in the same group as <1,2,3,4,5>, because eventually you want to compare members of the same group to see if you can factor their signs. So when you do the coordinate sort, you want to ignore the sign.

Sign-factoring

OK, so now you divided your coordinates into potential permutation sets. Now what? The next step, at least the way I chose to do it, is to factor the sign. This is easy: we look for two coordinates of the form <A,B,C,D,E> and <A,B,C,D,-E>, and combine them into <A,B,C,D,±E>. That is to say, find a pair in your permutation set whose coordinates are all identical except for one, which differ only in sign. In order to do this, you want to sort within your permutation set so that vectors with identical coordinates up to change of sign are sorted together. (I.e., you want <1,2,3,4,5> and <1,2,3,4,-5> to appear together, and <2,3,4,5,1> to appear separately). This can be accomplished by a custom vector comparison function that you use to sort coordinates, so that as you sort input coordinates in the first step, they are also put into the right order within each permutation set (to save the cost of having to do another sort within each set).

Now, one trick here is that you want to be able to represent the ± as a distinct kind of sign in your vector representation, so that after you have sign-factored four coordinates, <1,2,3,4,±5> and <1,2,3,-4,±5>, you want to be able to detect that the last coordinate of both factored coordinates are the same (i.e. ±5), so that you can continue to factor these two into <1,2,3,±4,±5>. So a simple floating-point representation is not good enough; you must use an extended number representation that admits ± as a distinct "sign". Also, if you're working with floating-point input, it's a good idea to define a custom equality operator that considers two numbers equal if they are within a small number, EPSILON, of each other. The reason is that polytopes tend to have coordinates like <1,0,0,0> and <0,1,0,0>, and when you do permutation factoring, you don't want floating-point roundoff to treat 0.0000000000001 and 0.00000000000002 as different numbers.

So anyway, you just repeatedly sign-factor within a permutation set until there are no more factorable pairs to be found. You can probably apply some clever algorithm here so that you don't end up with an O(n

^{2}) algorithm that scans the set many times over. For me, I used C++ STL's multimap container with a custom comparison function that always puts vectors with ± at the front of the set (and sorts them in such a way that vectors that differ in sign in exactly one coordinate, the kind that can be factored, are very likely to appear next to each other). This way, it's quite easy to find factorable pairs of vectors.

Factoring permutations

You do this until the permutation set can no longer be sign-factored, at which point you have something like this in your permutation set: <±1, ±2, ±3>, <±2, ±3, ±1>, <±3, ±1, ±2>. Now you are ready to factor the permutation. Your custom sorting function should be written in such a way that elements in your permutation set appear in lexicographical order. Why? Because there is an excellent known algorithm for enumerating permutations in lexicographical order. What we do at this stage is very simple: assume the set is in lexicographical order, then make a copy of the first vector in the set, and start enumerating its permutations. As you do so, check the remaining vectors in sequence; if they exactly match the enumerated permutations, then you can replace the entire set with either AP or EP (All Permutations, or Even Permutations). So for example, a set like <0,0,±1>, <0,±1,0>, <±1,0,0> can be replaced by ap<0,0,±1>. Then, if every coordinate has a ±, you can remove all the ±'s and write apacs<0,0,1>.

So how do you enumerate all permutations and even permutations in lexicographical order? This is how.

If you're clever, you can combine AP and EP recognition into a single pass: modify the algorithm described in the above page, so that instead of only returning even permutations, it returns all permutations but also tells you whether each permutation is even or odd. Then as you enumerate, if all the odd permutations are missing then you know it's an EP; if all permutations are present then it's an AP.

Repeat this for each permutation set and you got a nicely-factored form for your coordinates that you can post on your homepage without ending up with a 1-pixel scrollbar. For example, using this algorithm I managed to reduce the 3600 vertices of the bitruncated 120-cell into 22 apacs/epacs expressions. Otherwise, the coordinates wouldn't fit on the page!

Hope y'all found this helpful.

P.S. Of course, permutation factoring is just one part of the story... the other part is how to get nice coordinates like φ and φ

^{2}instead of just 1.6180339887 and 2.6180339887 (or ugly-looking things like (1+sqrt(5))/2 and (3+sqrt(5))/2 if you're using something like mathcad). That belongs in another post, which I'll share if I continue feeling nice and generous.