## "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
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)
```