"Fossies" - the Fresh Open Source Software Archive

Member "NZMATH-1.2.0/nzmath/permute.py" (19 Nov 2012, 21287 Bytes) of package /linux/misc/old/NZMATH-1.2.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. For more information about "permute.py" see the Fossies "Dox" file reference documentation.

    1 import random
    2 import nzmath.combinatorial as combinatorial
    3 import nzmath.gcd as gcd
    4 import nzmath.matrix as matrix
    5 import nzmath.rational as rational
    6 
    7 class Permute:
    8 
    9     """
   10     This is a class for 'normal' type element in the permutation group.
   11     Example, [2,3,1,5,4]
   12     This means [1 2 3 4 5]
   13                [2 3 1 5 4]
   14     (It is 1:1 onto mapping, 1->2, 2->3, 3->1, 4->5, 5->4)
   15     """
   16 
   17     def __init__(self, value, key=None, flag=False):
   18         """
   19         You can initialize with various one-to-one onto mapping.
   20         Example,
   21         Permute([2,3,4,5,1]) -> normal type
   22         Permute([3,4,2,1,0], 0) -> [4,5,3,2,1]-normal type(index start with 0)
   23         Permute(['b','c','d','e','a'], 1) -> [2,3,4,5,1]-normal type(identity is ascending order)
   24         Permute(['b','c','d','e','a'], -1) -> [4,3,2,1,5]-normal type(identity is descending order)
   25         Permute(['b','c','d','e','a'], ['b','a', 'c','d','e']) -> [1,3,4,5,2]-normal type(identity=key)
   26         Permute({'a':'b','b':'c','c':'d','d':'e','e':'a'}) -> [2,3,4,5,1]-normal type
   27         """
   28         if isinstance(value, dict):
   29             if key:
   30                 raise TypeError("cannot convert Permute. I think `key` should be None.")
   31             data = value.values()
   32             key = value.keys()
   33         elif isinstance(value, (list, tuple)):
   34             data = list(value)
   35         else:
   36             raise TypeError("cannot convert Permute. `value` should be a list or a dict.")
   37         if key == 0:
   38             self.data = [i + 1 for i in data]
   39             self.key = range(len(data))
   40         elif key:
   41             if isinstance(key, (list, tuple)):
   42                 self.key = list(key)
   43                 if len(value) != len(key):
   44                     raise TypeError("cannot convert Permute. The length of `key` should be equal to that of `value`.")
   45             elif key == 1:
   46                 p_key = list(data)
   47                 p_key.sort()
   48                 self.key = p_key
   49             elif key == -1:
   50                 p_key = list(data)
   51                 p_key.sort()
   52                 p_key.reverse()
   53                 self.key = p_key
   54             else:
   55                 raise TypeError("cannot convert Permute. `key` should be a list.")
   56             key = self.key
   57             if flag:
   58                 self.data = data
   59             else:
   60                 self.data = [key.index(x) + 1 for x in data]
   61         else:
   62             self.data = data
   63             self.key = range(1, len(data) + 1)
   64         data = self.data
   65         p_data = range(len(data))
   66         for x in data:
   67             if not rational.isIntegerObject(x):
   68                 raise TypeError("cannot convert Permute. `flag` should be False.")
   69             elif x <= 0 or x > len(data):
   70                 raise TypeError("cannot convert Permute. The map should be onto.")
   71             elif p_data[x-1] == -1:
   72                 raise ValueError("cannot convert Permute. The map should be one-to-one.")
   73             else:
   74                 p_data[x-1] = -1
   75 
   76     def __getitem__(self, other):
   77         try:
   78             idx = self.key.index(other)
   79         except ValueError:
   80             raise ValueError("The indices must be elements of self.key.")
   81         return self.key[self.data[idx]  - 1]
   82 
   83     def __mul__(self, other):
   84         """
   85         Compute the multiplication, that is, the composite of two maps self \circ other.
   86         The map is the application of `self` to the result of `other`.
   87         """
   88         s_data = self.data
   89         o_data = other.data
   90         lth = len(s_data)
   91         if self.key != other.key or lth != len(o_data):
   92             raise TypeError("cannot multiply a Permute by a Permute which has a different type.")
   93         sol = [s_data[o_data[i] - 1] for i in range(lth)]
   94         return Permute(sol, self.key, flag=True)
   95 
   96     def __rmul__(self, other):
   97         return other * self
   98 
   99     def __div__(self, other):
  100         return self * (other.inverse())
  101 
  102     __truediv__ = __div__
  103 
  104     def __rdiv__(self, other):
  105         return other * (self.inverse())
  106 
  107     def __pow__(self, other):
  108         sol = self.__class__(self.data, self.key, flag=True)
  109         if not rational.isIntegerObject(other):
  110             raise TypeError("cannot pow operation with %s" % other)
  111         if other > 0:
  112             for i in range(other - 1):
  113                 sol = self * sol
  114         else:
  115             inv = self.inverse()
  116             for i in range(abs(other) + 1):
  117                 sol = inv * sol
  118         return sol
  119 
  120     def __call__(self, other):
  121         return self.permute(other)
  122 
  123     def setKey(self, key=None):
  124         """
  125         Set other key.
  126         The function may be used if you want to permute a different sequence with
  127         the same permutation.
  128         """
  129         if key == 0:
  130             self.key = range(len(data))
  131         elif key:
  132             if len(key) != len(self.key):
  133                 raise TypeError, "The length of `key` should be equal to that of self.key."
  134             else:
  135                 if key[0] in self.key: # key transformation
  136                     data = list(self.data)
  137                     keys = self.key
  138                     sol = [0] * len(data)
  139                     try:
  140                         for i in range(len(data)):
  141                             sol[key.index(keys[i])] = key.index(keys[data[i]-1]) + 1
  142                         self.data = sol
  143                     except ValueError:
  144                         pass
  145                 self.key = key
  146         else:
  147             self.key = range(1, len(data) + 1)
  148 
  149     def getValue(self):
  150         """
  151         Return value of self.
  152         """
  153         return [self.key[self.data[i] - 1] for i in range(len(self.data))]
  154 
  155     def inverse(self):
  156         s_data = self.data
  157         sol = [0] * len(s_data)
  158         for i in range(len(s_data)):
  159             sol[s_data[i] - 1] = i+1
  160         return Permute(sol, self.key, flag=True)
  161 
  162     def getGroup(self):
  163         return PermGroup(self.key)
  164 
  165     def numbering(self):
  166         """
  167         Return the number of self by the following numbering.
  168 
  169         This is the inductive definition on the dimension.
  170         It is symmetrical arranging.
  171 
  172         Example,
  173         2-dimension [1,2], [2,1]
  174         3-dimension [1,2,3], [2,1,3], [1,3,2], [2,3,1], [3,1,2], [3,2,1]
  175         4-dimension [1,2,3,4], [2,1,3,4], [1,3,2,4], [2,3,1,4], [3,1,2,4],
  176                     [3,2,1,4], ..., [4,3,2,1]
  177         """
  178         s_data = self.data
  179         val = [-1] * (len(s_data))
  180         for i in range(len(s_data)):
  181             val[s_data[i] - 1] = 0
  182             for j in range(s_data[i], len(val)):
  183                 if val[j] != -1:
  184                     val[j] += 1
  185         sol = 0
  186         val[0] = 1
  187         for j in range(len(val) - 1, -1, -1):
  188             sol = (j+1) * sol + val[j]
  189         return sol
  190 
  191     def order(self):
  192         """
  193         This method returns order for permutation element.
  194         """
  195         return self.ToCyclic().order()
  196 
  197     def ToTranspose(self):
  198         """
  199         This method returns
  200          2-dimensional cyclic type element of permutation group.
  201 
  202         The method uses recursion.
  203         """
  204         s_data = list(self.data)
  205         lth = len(s_data)
  206         if lth == 1:
  207             return ExPermute(1, [])
  208         else:
  209             sol = []
  210             if s_data[lth - 1] != lth:
  211                 sol.append((s_data[lth - 1], lth))
  212                 s_data[s_data.index(lth)] = s_data[lth - 1]
  213             sol.extend((Permute(s_data[:lth - 1]).ToTranspose()).data)
  214             return ExPermute(lth, sol, self.key, flag=True)
  215 
  216     def ToCyclic(self):
  217         """
  218         This method returns cyclic type element of permutation group.
  219         """
  220         s_data = self.data
  221         box = list(self.data)
  222         sol = []
  223         for i in range(len(s_data)):
  224             if box[i] != '*':
  225                 p_sol = [(i+1)]
  226                 box[i] = '*'
  227                 j = i
  228                 while s_data[j] != i+1:
  229                     p_sol.append(s_data[j])
  230                     j = s_data[j] - 1
  231                     box[j] = '*'
  232                 if len(p_sol) != 1:
  233                     sol.append(tuple(p_sol))
  234         return ExPermute(len(s_data), sol, self.key, flag=True)
  235 
  236     def sgn(self):
  237         """
  238         This method returns sign.
  239         
  240         If self is even permutation, that is, self can be written as a composition
  241         of an even number of transpositions, it returns 1. Otherwise,that is, for odd
  242         permutation, it returns -1.
  243         """
  244         return self.ToCyclic().sgn()
  245 
  246     def types(self):
  247         """
  248         This method returns 'type' defined by each cyclic element length.
  249         """
  250         c_data = self.ToCyclic().data
  251         sol = [len(c_data[i]) for i in range(len(c_data))]
  252         sol.sort()
  253         return sol
  254 
  255     def ToMatrix(self):
  256         """
  257         This method returns the permutation matrix.
  258         """
  259         lth = len(self.data)
  260         A = matrix.SquareMatrix(lth)
  261         for j in range(lth):
  262             A[j+1, self.data[j]] = 1
  263         return A
  264 
  265     def permute(self, lists):
  266         """
  267         permute list following with self permutation.
  268 
  269         Warning: The method do not check the compatibility of `lists` and self.key (except dict type).
  270         """
  271         if len(lists) != len(self.data):
  272             raise TypeError, "The length of `lists` should be equal to that of self.key."
  273         if isinstance(lists, dict):
  274             sol = {}
  275             key = self.key
  276             for x in lists.keys():
  277                 sol[key[self.data[key.index(x)] - 1]] = lists[x]
  278         elif isinstance(lists, (list, tuple)):
  279             sol = [0] * len(lists)
  280             for i in range(len(lists)):
  281                 sol[self.data[i] - 1] = lists[i]
  282         return sol
  283 
  284     def __eq__(self, other):
  285         s_data = self.data
  286         o_data = other.data
  287         lth = len(s_data)
  288         if self.key != other.key or lth != len(o_data):
  289             return False
  290         for i in range(lth):
  291             if s_data[i] != o_data[i]:
  292                 return False
  293         return True
  294 
  295     def __ne__(self, other):
  296         return not self == other
  297 
  298     def __repr__(self):
  299         return repr(self.key)+" -> "+repr(self.getValue())
  300 
  301     def __str__(self):
  302         return str(self.key)+" -> "+str(self.getValue())
  303 
  304 
  305 class ExPermute:
  306 
  307     """
  308     This is a class for cyclic type element of permutation group.
  309     Example, (5, [(1, 2), (3, 4)])
  310     This means (1, 2)(3, 4)=[2, 1, 4, 3, 5]
  311     """
  312 
  313     def __init__(self, dim, value, key=None, flag=False):
  314         if not (rational.isIntegerObject(dim) and isinstance(value, list)):
  315             raise TypeError("cannot convert ExPermute. `dim` should be an integer and `value` should be a list.")
  316         self.dim = dim
  317         data = value
  318         self.data = []
  319         if key == 0:
  320             self.key = range(dim)
  321             for x in data:
  322                 ele = [ y + 1 for y in x ]
  323                 self.data.append(tuple(ele))
  324         elif key:
  325             if isinstance(key, (list, tuple)):
  326                 self.key = list(key)
  327                 if dim != len(key):
  328                     raise TypeError("cannot convert ExPermute. The length of `key` should be equal to dim.")
  329             else:
  330                 raise TypeError("cannot convert ExPermute. `key` should be a list or a tuple.")
  331             key = self.key
  332             if flag:
  333                 self.data = data
  334             else:
  335                 for x in data:
  336                     ele = [key.index(x[i]) + 1 for i in range(len(x))]
  337                     self.data.append(tuple(ele))
  338         else:
  339             self.data = data
  340             self.key = range(1, dim + 1)
  341         data = self.data
  342         for x in data:
  343             if not isinstance(x, tuple):
  344                 raise TypeError("cannot convert ExPermute. `flag` should be False.")
  345             box = range(dim)
  346             for y in x:
  347                 if (y > dim) or (y <= 0):
  348                     raise TypeError("cannot convert ExPermute. The map should be onto.")
  349                 elif box[y-1] == -1:
  350                     raise ValueError("cannot convert ExPermute. The map should be one-to-one.")
  351                 else:
  352                     box[y-1] = -1
  353 
  354     def __getitem__(self, other):
  355         try:
  356             idx = self.key.index(other)
  357         except ValueError:
  358             raise ValueError("The indices must be elements of self.key.")
  359         val = idx + 1
  360         for i in range(len(self.data) - 1, -1, -1):
  361             data_i = list(self.data[i])
  362             try:
  363                 pla = data_i.index(val)
  364                 val = data_i[(pla+1) % len(data_i)]
  365             except ValueError:
  366                 pass
  367         return self.key[val - 1]
  368 
  369     def __mul__(self, other):
  370         if self.key != other.key or self.dim != other.dim:
  371             raise TypeError("cannot multiply an ExPermute by an ExPermute which has a different type.")
  372         sol = [x for x in self.data] + [x for x in other.data]
  373         return ExPermute(self.dim, sol, self.key, flag=True)
  374 
  375     def __rmul__(self, other):
  376         return other * self
  377 
  378     def __div__(self, other):
  379         return self * other.inverse()
  380 
  381     __truediv__ = __div__
  382 
  383     def __rdiv__(self, other):
  384         return other * self.inverse()
  385 
  386     def __pow__(self, other):
  387         sol = ExPermute(self.dim, self.data, self.key, flag=True)  # other instance
  388         if not rational.isIntegerObject(other):
  389             raise TypeError("cannot pow operation with %s" % other)
  390         if other > 0:
  391             for i in range(other - 1):
  392                 sol = self * sol
  393         else:
  394             inv = self.inverse()
  395             for i in range(abs(other) + 1):
  396                 sol = inv * sol
  397         return sol
  398 
  399     def __call__(self, other):
  400         return self.permute(other)
  401 
  402     def setKey(self, key=None):
  403         """
  404         Set other key.
  405         The function may be used if you want to permute a different sequence with 
  406         the same permutation.
  407         """
  408         if key == 0:
  409             self.key = range(self.dim)
  410         elif key:
  411             if len(key) != self.dim:
  412                 raise TypeError, "The lenght of `key` should be equal to that of self.key."
  413             else:
  414                 if key[0] in self.key: # key transformation
  415                     data = list(self.data)
  416                     keys = self.key
  417                     sol = []
  418                     try:
  419                         for x in data:
  420                             p_ele = []
  421                             for i in range(len(x)):
  422                                 p_ele.append(key.index(keys[x[i]-1])+1)
  423                             sol.append(tuple(p_ele))
  424                         self.data = sol
  425                     except ValueError:
  426                         pass
  427                 self.key = key
  428         else:
  429             self.key = range(1, self.dim + 1)
  430 
  431     def getValue(self):
  432         """
  433         Return value of self.
  434         """
  435         out = []
  436         for x in self.data:
  437             out.append(tuple([self.key[x[i] - 1] for i in range(len(x))]))
  438         return out
  439 
  440     def inverse(self):
  441         s_data = list(self.data)
  442         s_data.reverse()
  443         for i in range(len(s_data)):
  444             ele_data = list(s_data[i])
  445             if len(s_data[i]) > 2:
  446                 ele_data.reverse()
  447             s_data[i] = tuple(ele_data)
  448         return ExPermute(self.dim, s_data, self.key, flag=True)
  449 
  450     def getGroup(self):
  451         return PermGroup(self.key)
  452 
  453     def order(self):
  454         """
  455         This method returns order for permutation element.
  456         """
  457         data = self.simplify().data
  458         sol = 1
  459         for x in data:
  460             sol = gcd.lcm(sol, len(x))
  461         return sol
  462 
  463     def ToNormal(self):
  464         """
  465         This method returns normal type element of permutation group.
  466         """
  467         dim = self.dim
  468         s_data = list(self.data)
  469         s_data.reverse()
  470         sol = ['*'] * dim
  471         for x in s_data:
  472             ele_data = list(x)
  473             ele_data.append(ele_data[0])
  474             trans_data = []
  475             for y in x:
  476                 if sol[y-1] != '*':
  477                     trans_data.append(sol.index(y))
  478                 else:
  479                     trans_data.append(y-1)
  480             for j in range(len(trans_data)):
  481                 sol[trans_data[j]] = ele_data[j+1]
  482                 if sol[trans_data[j]] == trans_data[j] + 1:
  483                     sol[trans_data[j]] = '*'
  484         for i in range(dim):
  485             if sol[i] == '*':
  486                 sol[i] = i+1
  487         return Permute(sol, self.key, flag=True)
  488 
  489     def simplify(self):
  490         """
  491         This method returns more simple element.
  492         """
  493         return self.ToNormal().ToCyclic()
  494 
  495     def sgn(self):
  496         """
  497         This method returns sign for permutation element.
  498 
  499         If self is even permutation, that is, self can be written as a composition
  500         of an even number of transpositions, it returns 1. Otherwise,that is, for odd
  501         permutation, it returns -1.
  502         """
  503         sol = 1
  504         for x in self.data:
  505             if len(x) & 1 == 0:
  506                 sol = -sol
  507         return sol
  508 
  509     def permute(self, lists):
  510         """
  511         permute list following with self permutation
  512         
  513         Warning: The method do not check the compatibility of `lists` and self.key (except dict type).
  514         """
  515         if len(lists) != self.dim:
  516             raise TypeError, "The length of `lists` should be equal to self.dim."
  517         if isinstance(lists, dict):
  518             sol = dict(lists)
  519             key = self.key
  520             data = self.data
  521             for i in range(len(data) - 1, -1, -1):
  522                 data_i = data[i]
  523                 first = key[data_i[0] - 1]
  524                 for j in range(len(data_i) - 1):
  525                     idx = key[data_i[j+1] - 1]
  526                     sol[first], sol[idx] = sol[idx], sol[first]
  527         elif isinstance(lists, (list, tuple)):
  528             sol = list(lists)
  529             data = self.data
  530             for i in range(len(data) - 1, -1, -1):
  531                 data_i = data[i]
  532                 first = data_i[0] - 1
  533                 for j in range(len(data[i]) - 1):
  534                     idx = data_i[j+1] - 1
  535                     sol[first], sol[idx] = sol[idx], sol[first]
  536         return sol
  537 
  538     def __eq__(self, other):
  539         if self.key != other.key or self.dim != other.dim:
  540             return False
  541         s_data = (self.simplify()).data
  542         o_data = (other.simplify()).data
  543         if len(s_data) != len(o_data):
  544             return False
  545         for i in range(len(s_data)):
  546             for j in range(len(s_data[i])):
  547                 if s_data[i][j] != o_data[i][j]:
  548                     return False
  549         return True
  550 
  551     def __ne__(self, other):
  552         return not self == other
  553 
  554     def __repr__(self):
  555         return repr(self.getValue()) + " <" + repr(self.key) + ">"
  556 
  557     def __str__(self):
  558         self.data = self.simplify().data
  559         return str(self.getValue()) + " <" + str(self.key) + ">"
  560 
  561 class PermGroup:
  562     """
  563     This is a class for permutation group.
  564     """
  565     def __init__(self, key):
  566         if isinstance(key, (int, long)):
  567             self.key = range(1, key + 1)
  568         elif isinstance(key, (list, tuple)):
  569             self.key = list(key)
  570         elif isinstance(key, dict):
  571             self.key = dict.keys()
  572         else:
  573             raise TypeError, "cannot convert PermGroup. `key` should be an integer or a list/tuple/dict."
  574 
  575     def __repr__(self):
  576         return repr(self.key)
  577 
  578     def __str__(self):
  579         return str(self.key)
  580 
  581     def __eq__(self, other):
  582         if self.key == other.key:
  583             return True
  584         else:
  585             return False
  586 
  587     def __ne__(self, other):
  588         return not(self == other)
  589 
  590     def card(self):
  591         return self.grouporder()
  592 
  593     def createElement(self, seed):
  594         """
  595         Create Permute or ExPermute with seed.
  596         createElement(dict) -> Permute(dict)
  597         createElement(tuple) -> Permute(list(tuple), self.key)
  598         createElement(key_element_list) -> Permute(key_element_list, self.key)
  599         createElement([cyclic_tuple,...]) -> ExPermute(len(self.key), [cyclic_tuple,...], self.key)
  600         """
  601         if isinstance(seed, dict):
  602             if set(self.key) == set(dict.keys()):
  603                 return Permute(seed)
  604             else:
  605                 raise TypeError, "`seed`.key should be equal to self.key."
  606         elif isinstance(seed, tuple):
  607             return Permute(list(seed). self.key)
  608         elif isinstance(seed, list):
  609             if seed[0] in self.key:
  610                 return Permute(seed, self.key)
  611             elif isinstance(seed[0], tuple):
  612                 return ExPermute(len(self.key), seed, self.key)
  613         raise TypeError, "`seed` should be a dict/tuple/list."
  614 
  615     def identity(self):
  616         return Permute(self.key, self.key)
  617 
  618     def identity_c(self):
  619         """
  620         Return identity for cyclic type.
  621         """
  622         return ExPermute(len(self.key), [], self.key)
  623 
  624     def grouporder(self):
  625         return combinatorial.factorial(len(self.key))
  626 
  627     def randElement(self):
  628         """
  629         Create random Permute type element.
  630         """
  631         copy = list(self.key)
  632         sol = []
  633         while copy:
  634             sol.append(copy.pop(random.randrange(len(copy))))
  635         return Permute(sol, self.key)