Factoring out permutations of SN
 
  
 
 
     
 
 
 
 
 
 
 
    
        
        asked 7 years ago  
 
 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?
 
Preview: (hide)
 
 
 
 
          
 
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 (
    
        7 years ago
    )
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 (
    
        7 years ago
    )
add a comment