Fast cardinality method for IntegerVectorsModPermutationGroup #36787
Description
Problem Description
IntegerVectorsModPermutationGroup has no implementation of cardinality, so it defaults to iterating over the whole set and tallying. This is obviously slow for large sets.
For example, with vectors of length 10, summing to 20, and with the permutation group where the first two elements can be swapped, it takes more than two minutes to compute the cardinality.
Proposed Solution
The cardinality should be calculated using the cycle index theorem (see e.g. Peter Cameron's blog post for an explanation).
An example code is here. This should be more or less a ready plug-in for the cardinality method.
def fast_cardinality(self):
G = self._permgroup
k = G.degree() # Number of boxes
d = self._sum # Number of balls
m = self._max_part # Maximum balls in one box, -1 for no limit
if m == -1:
m = d
if k==0:
# Special case, no boxes.
if d==0:
return 1
else:
return 0
# Power series with enough precision
R.<x> = PowerSeriesRing(QQ, default_prec = d+1)
# The function-counting series, for maximum part size m, is
# (1-t^(m+1)) / (1-t) = 1+t+...+t^m.
#
# For the figure-counting series, we substitute x^cyclen for t.
Z = G.cycle_index()
funcount = sum(coeff * prod((1-x^((m+1)*cyclen)) / (1-x^cyclen)
for cyclen in cyctype)
for (cyctype, coeff) in Z)
# Extract the x^d coefficient.
dic = funcount.dict()
if d in dic:
return Integer(dic[d]) # Convert from Rational to Integer
else:
return 0
Alternatives Considered
We could leave it as is, and rely on users to perform the cycle index calculations.
Additional Information
Here is a speed comparison.
Permutation group acting on 10 elements, and only containing two permutations, the trivial one and the swap (1,2). Count the vectors that sum to 20.
The times are about 0.1 seconds versus 161 seconds.
sage: G=PermutationGroup([(1,2)],domain=range(10)); V=IntegerVectorsModPermutationGroup(G,20)
sage: t0=time(); fast_cardinality(V), time()-t0
(5911763, 0.09431600570678711)
sage: t0=time(); V.cardinality(), time()-t0
(5911763, 160.82350969314575)
sage: version()
'SageMath version 9.0, Release Date: 2020-01-01'
Is there an existing issue for this?
- I have searched the existing issues for a bug report that matches the one I want to file, without success.