Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download
241818 views
Tweet
Share
Share
1
# -*- coding: utf-8 -*-

2
r"""

3
Algorithms for use together with MySubgroup -- an extension to the standard implementation of subgroups of the modular group.

4


5
AUTHOR:

6


7
 - Fredrik Stroemberg

8


9
 

10


11


12
"""

13
#*****************************************************************************

14
#  Copyright (C) 2010 Fredrik Strömberg <[email protected]>,

15
#

16
#  Distributed under the terms of the GNU General Public License (GPL)

17
#

18
#    This code is distributed in the hope that it will be useful,

19
#    but WITHOUT ANY WARRANTY; without even the implied warranty of

20
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

21
#    General Public License for more details.

22
#

23
#  The full text of the GPL is available at:

24
#

25
#                  http://www.gnu.org/licenses/

26
#****************************************************************************

27


28
include "sage/ext/interrupt.pxi"  # ctrl-c interrupt block support

29
include "sage/ext/stdsage.pxi"  # ctrl-c interrupt block support

30
include "sage/ext/cdefs.pxi"

31


32
from copy import deepcopy

33
from sage.combinat.permutation import Permutation_class

34
from sage.groups.perm_gps.permgroup_element import PermutationGroupElement

35


36
def are_transitive_permutations(E,R):

37
    r""" Check that E,R are transitive permutations, i.e. that <E,R>=S_N

38


39
    INPUT:

40


41
         - ``E`` -- permutation on N letters 

42
         - ``R`` -- permutation on N letters

43


44
             - E and R can be in any of the following formats:

45


46
                 - list [a1,a2,...,aN]

47
                 - member of Permutations(N)

48
                 - member of SymmetricGroup(N)

49


50
     OUTPUT:

51


52
     - bool  

53


54


55
     EXAMPLES::

56


57
         sage: E=Permutations(4)([1,2,4,3]); E.to_cycles()

58
         [(1,), (2,), (3, 4)]

59
         sage: R=Permutations(4)([2,1,3,4]); R.to_cycles()

60
         [(1, 2), (3,), (4,)]

61
         sage: are_transitive_permutations(E,R)

62
         False

63
         sage: R=Permutations(4)([2,3,1,4]); R.to_cycles()

64
         [(1, 2, 3), (4,)]

65
         sage: are_transitive_permutations(E,R)

66
         True

67
         sage: ES=SymmetricGroup(4)([1,2,4,3]);ES

68
         (3,4)

69
         sage: ER=SymmetricGroup(4)([2,3,1,4]);ER

70
         (1,2,3)

71
         sage: are_transitive_permutations(ES,RS)

72
         True

73


74
    """

75
    gotten=list()    

76
    t0=isinstance(E,list)

77
    if(t0):

78
        El=E; Rl=R

79
    else:

80
        t1=isinstance(E,Permutation_class) # constructed from Permutations(N)

81
        if(t1):

82
            El=list(E)

83
            Rl=list(R)

84
        else:

85
            t2=isinstance(E,PermutationGroupElement) # constructed from SymmetricGroup(N)

86
            if(t2):

87
                El=E.list()

88
                Rl=R.list()           

89
            else:

90
                raise TypeError, "Indata need to be Permuatations! Got E=%s of type=%s" %(E,type(E))

91
    N=len(El)

92
    gotten.append(Rl[0])

93
    gotten0=deepcopy(gotten)

94
    for j in range(N):

95
        for x in gotten0:

96
            y=El[x-1]

97
            if(gotten.count(y)==0):

98
                gotten.append(y)

99
            yy=Rl[y-1]

100
            if(gotten.count(yy)==0):

101
                gotten.append(yy)

102
            yyy=Rl[yy-1]

103
            if(gotten.count(yyy)==0):

104
                gotten.append(yyy)

105
        if(gotten0==gotten):

106
            if(len(gotten)<>N):

107
                return False

108
            else:

109
                return True

110
        gotten0=deepcopy(gotten)

111
    return False

112


113


114


115


116


117