Factoring out permutations of SN

asked 2018-03-14 13:52:42 +0200

LAV gravatar image

I'm trying to remove certain permutations from S_N.

I want to remove all permutations that leave the first [0...k[ indices invariant (except for Identity element). So what I'm looking for is S_{1,.., N} / S_{k, .., N}.

I understand that I could do ( N= 10, k=5 ) 

SN = SymmetricGroup(range(10))
SkN = SymmetricGroup(range(5,10)
permutations = [sigma for sigma in SN if sigma not in SkN]

but this is extremely slow. My goal here is to speed up my code and I end up generating twice as much permutations and doing extreme list checking.

I'm pretty sure people were smart enough to implement a feature that gives me back a generator Squotient = SN/SkN, but I could not find this in the documentation. Any ideas?

edit retag flag offensive close merge delete

Comments

Please describe the needed object, and its type, and its further use. So far, one can give as answer for the one or the other line as follows:

(1) The list S in

sage: K, N = 3, 6    # other values
sage: S = [s for s in SymmetricGroup(range(N)) if [s(k) for k in [0..K-1]] != [0..K-1] ]
sage: len(S) == factorial(N) - factorial(K)
True

so that it must be also stored as a list.

(2) The left/right quotient in

sage: len( G.cosets(H, side='right') ), len( G.cosets(H, side='right') )
(120, 120)

Stored again.

(3) A generator for the one or the other list.

(4) A "programming device" to loop over SN and do something for some $s$ if not in SkN, e.g.

for s in SN:
    if [s(k) for k in [0..K-1]] == [0..K-1]:
        continue
    # real work
dan_fulea gravatar imagedan_fulea ( 2018-03-14 20:41:43 +0200 )edit

Thank you, (2) is what I was looking for, but I expected it would not return a list and return an iterator instead. (1) and (4) seems the most appropriate.

LAV gravatar imageLAV ( 2018-03-15 13:36:05 +0200 )edit
add a comment