random_element for colored and signed permutations

[mantepse]

Before this ticket,

sage: SignedPermutations(10).random_element()

takes forever.

Component: combinatorics

Author: Martin Rubey

Branch/Commit: u/mantepse/random_element_for_colored_and_signed_permutations @ 86d9ac7

Issue created by migration from https://trac.sagemath.org/ticket/34925

[mantepse]

Branch: u/mantepse/random_element_for_colored_and_signed_permutations

[mantepse]

Author: Martin Rubey

[mantepse]

Commit: 86d9ac7

[mantepse]

New commits:

86d9ac7

random_element for colored and signed permutations

[mantepse]

comment:3

There is a design decision for SignedPermutations I do not understand: it inherits from ColoredPermutations, but the colors are {+1, -1} instead of IntegerModRing(2).

In fact, also IntegerModRing looks strange to me, because we really only consider the colors as a group, not a ring.

It seems to me that the only reason for this is the result of SignedPermutation.colors(). However, this choice requires us to implement very many methods twice.

I see a few possibilities:

1. keep the decision and ignore its downsides
2. introduce a group containing two elements {1, -1}.
3. only override SignedPermutation.colors().
4. change the colors to {0, 1}.

[tscrim]

The issue for this ticket (mostly just for the official record) comes from the fact it is using the default random_element() that lists all the elements and pulls a random element from that.

At some point, we probably should also implement an unrank() and __getitem__ method since that is also easy. I just unrolled the unrank() for the Cartesian product.

def unrank(n):
    k = self._m * self._n
    N = n // k
    perm = self._P.unrank(N)
    colors = [None] * self._n
    C = n % k
    for i in range(self._n-1,-1,-1):
        colors[i] = self._C.unrank(C % self._m)
        C //= self._m
    return self.element_class(self, tuple(colors), perm) 

Some comments about the design:

Since IntegerModRing is a ring, it is also naturally a group (under +). Plus it is fast.

The colors themselves don't need to be an actual elements of a group parent since they are used internally. If it helps, you can think of them as elements in a facade parent. It is more natural for the type B Weyl/Coxeter group combinatorics people to work with {1, -1} as the "colors", and there isn't too much extra that needs to be most-duplicated IIRC. If this ends up scaling to a bigger problem, then we can revisit the design and see if we can remove the duplication.