ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 15 Mar 2018 13:36:05 +0100Factoring out permutations of SNhttps://ask.sagemath.org/question/41538/factoring-out-permutations-of-sn/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?Wed, 14 Mar 2018 13:52:42 +0100https://ask.sagemath.org/question/41538/factoring-out-permutations-of-sn/Comment by dan_fulea for <p>I'm trying to remove certain permutations from S_N.</p>
<p>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}. </p>
<p>I understand that I could do ( N= 10, k=5 ) </p>
<pre><code>SN = SymmetricGroup(range(10))
SkN = SymmetricGroup(range(5,10)
permutations = [sigma for sigma in SN if sigma not in SkN]
</code></pre>
<p>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. </p>
<p>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?</p>
https://ask.sagemath.org/question/41538/factoring-out-permutations-of-sn/?comment=41549#post-id-41549Please 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 workWed, 14 Mar 2018 20:41:43 +0100https://ask.sagemath.org/question/41538/factoring-out-permutations-of-sn/?comment=41549#post-id-41549Comment by LAV for <p>I'm trying to remove certain permutations from S_N.</p>
<p>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}. </p>
<p>I understand that I could do ( N= 10, k=5 ) </p>
<pre><code>SN = SymmetricGroup(range(10))
SkN = SymmetricGroup(range(5,10)
permutations = [sigma for sigma in SN if sigma not in SkN]
</code></pre>
<p>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. </p>
<p>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?</p>
https://ask.sagemath.org/question/41538/factoring-out-permutations-of-sn/?comment=41565#post-id-41565Thank 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.Thu, 15 Mar 2018 13:36:05 +0100https://ask.sagemath.org/question/41538/factoring-out-permutations-of-sn/?comment=41565#post-id-41565