Coverage for /usr/lib/python3/dist-packages/sympy/combinatorics/permutations.py: 24%
792 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1import random
2from collections import defaultdict
3from collections.abc import Iterable
4from functools import reduce
6from sympy.core.parameters import global_parameters
7from sympy.core.basic import Atom
8from sympy.core.expr import Expr
9from sympy.core.numbers import Integer
10from sympy.core.sympify import _sympify
11from sympy.matrices import zeros
12from sympy.polys.polytools import lcm
13from sympy.printing.repr import srepr
14from sympy.utilities.iterables import (flatten, has_variety, minlex,
15 has_dups, runs, is_sequence)
16from sympy.utilities.misc import as_int
17from mpmath.libmp.libintmath import ifac
18from sympy.multipledispatch import dispatch
20def _af_rmul(a, b):
21 """
22 Return the product b*a; input and output are array forms. The ith value
23 is a[b[i]].
25 Examples
26 ========
28 >>> from sympy.combinatorics.permutations import _af_rmul, Permutation
30 >>> a, b = [1, 0, 2], [0, 2, 1]
31 >>> _af_rmul(a, b)
32 [1, 2, 0]
33 >>> [a[b[i]] for i in range(3)]
34 [1, 2, 0]
36 This handles the operands in reverse order compared to the ``*`` operator:
38 >>> a = Permutation(a)
39 >>> b = Permutation(b)
40 >>> list(a*b)
41 [2, 0, 1]
42 >>> [b(a(i)) for i in range(3)]
43 [2, 0, 1]
45 See Also
46 ========
48 rmul, _af_rmuln
49 """
50 return [a[i] for i in b]
53def _af_rmuln(*abc):
54 """
55 Given [a, b, c, ...] return the product of ...*c*b*a using array forms.
56 The ith value is a[b[c[i]]].
58 Examples
59 ========
61 >>> from sympy.combinatorics.permutations import _af_rmul, Permutation
63 >>> a, b = [1, 0, 2], [0, 2, 1]
64 >>> _af_rmul(a, b)
65 [1, 2, 0]
66 >>> [a[b[i]] for i in range(3)]
67 [1, 2, 0]
69 This handles the operands in reverse order compared to the ``*`` operator:
71 >>> a = Permutation(a); b = Permutation(b)
72 >>> list(a*b)
73 [2, 0, 1]
74 >>> [b(a(i)) for i in range(3)]
75 [2, 0, 1]
77 See Also
78 ========
80 rmul, _af_rmul
81 """
82 a = abc
83 m = len(a)
84 if m == 3:
85 p0, p1, p2 = a
86 return [p0[p1[i]] for i in p2]
87 if m == 4:
88 p0, p1, p2, p3 = a
89 return [p0[p1[p2[i]]] for i in p3]
90 if m == 5:
91 p0, p1, p2, p3, p4 = a
92 return [p0[p1[p2[p3[i]]]] for i in p4]
93 if m == 6:
94 p0, p1, p2, p3, p4, p5 = a
95 return [p0[p1[p2[p3[p4[i]]]]] for i in p5]
96 if m == 7:
97 p0, p1, p2, p3, p4, p5, p6 = a
98 return [p0[p1[p2[p3[p4[p5[i]]]]]] for i in p6]
99 if m == 8:
100 p0, p1, p2, p3, p4, p5, p6, p7 = a
101 return [p0[p1[p2[p3[p4[p5[p6[i]]]]]]] for i in p7]
102 if m == 1:
103 return a[0][:]
104 if m == 2:
105 a, b = a
106 return [a[i] for i in b]
107 if m == 0:
108 raise ValueError("String must not be empty")
109 p0 = _af_rmuln(*a[:m//2])
110 p1 = _af_rmuln(*a[m//2:])
111 return [p0[i] for i in p1]
114def _af_parity(pi):
115 """
116 Computes the parity of a permutation in array form.
118 Explanation
119 ===========
121 The parity of a permutation reflects the parity of the
122 number of inversions in the permutation, i.e., the
123 number of pairs of x and y such that x > y but p[x] < p[y].
125 Examples
126 ========
128 >>> from sympy.combinatorics.permutations import _af_parity
129 >>> _af_parity([0, 1, 2, 3])
130 0
131 >>> _af_parity([3, 2, 0, 1])
132 1
134 See Also
135 ========
137 Permutation
138 """
139 n = len(pi)
140 a = [0] * n
141 c = 0
142 for j in range(n):
143 if a[j] == 0:
144 c += 1
145 a[j] = 1
146 i = j
147 while pi[i] != j:
148 i = pi[i]
149 a[i] = 1
150 return (n - c) % 2
153def _af_invert(a):
154 """
155 Finds the inverse, ~A, of a permutation, A, given in array form.
157 Examples
158 ========
160 >>> from sympy.combinatorics.permutations import _af_invert, _af_rmul
161 >>> A = [1, 2, 0, 3]
162 >>> _af_invert(A)
163 [2, 0, 1, 3]
164 >>> _af_rmul(_, A)
165 [0, 1, 2, 3]
167 See Also
168 ========
170 Permutation, __invert__
171 """
172 inv_form = [0] * len(a)
173 for i, ai in enumerate(a):
174 inv_form[ai] = i
175 return inv_form
178def _af_pow(a, n):
179 """
180 Routine for finding powers of a permutation.
182 Examples
183 ========
185 >>> from sympy.combinatorics import Permutation
186 >>> from sympy.combinatorics.permutations import _af_pow
187 >>> p = Permutation([2, 0, 3, 1])
188 >>> p.order()
189 4
190 >>> _af_pow(p._array_form, 4)
191 [0, 1, 2, 3]
192 """
193 if n == 0:
194 return list(range(len(a)))
195 if n < 0:
196 return _af_pow(_af_invert(a), -n)
197 if n == 1:
198 return a[:]
199 elif n == 2:
200 b = [a[i] for i in a]
201 elif n == 3:
202 b = [a[a[i]] for i in a]
203 elif n == 4:
204 b = [a[a[a[i]]] for i in a]
205 else:
206 # use binary multiplication
207 b = list(range(len(a)))
208 while 1:
209 if n & 1:
210 b = [b[i] for i in a]
211 n -= 1
212 if not n:
213 break
214 if n % 4 == 0:
215 a = [a[a[a[i]]] for i in a]
216 n = n // 4
217 elif n % 2 == 0:
218 a = [a[i] for i in a]
219 n = n // 2
220 return b
223def _af_commutes_with(a, b):
224 """
225 Checks if the two permutations with array forms
226 given by ``a`` and ``b`` commute.
228 Examples
229 ========
231 >>> from sympy.combinatorics.permutations import _af_commutes_with
232 >>> _af_commutes_with([1, 2, 0], [0, 2, 1])
233 False
235 See Also
236 ========
238 Permutation, commutes_with
239 """
240 return not any(a[b[i]] != b[a[i]] for i in range(len(a) - 1))
243class Cycle(dict):
244 """
245 Wrapper around dict which provides the functionality of a disjoint cycle.
247 Explanation
248 ===========
250 A cycle shows the rule to use to move subsets of elements to obtain
251 a permutation. The Cycle class is more flexible than Permutation in
252 that 1) all elements need not be present in order to investigate how
253 multiple cycles act in sequence and 2) it can contain singletons:
255 >>> from sympy.combinatorics.permutations import Perm, Cycle
257 A Cycle will automatically parse a cycle given as a tuple on the rhs:
259 >>> Cycle(1, 2)(2, 3)
260 (1 3 2)
262 The identity cycle, Cycle(), can be used to start a product:
264 >>> Cycle()(1, 2)(2, 3)
265 (1 3 2)
267 The array form of a Cycle can be obtained by calling the list
268 method (or passing it to the list function) and all elements from
269 0 will be shown:
271 >>> a = Cycle(1, 2)
272 >>> a.list()
273 [0, 2, 1]
274 >>> list(a)
275 [0, 2, 1]
277 If a larger (or smaller) range is desired use the list method and
278 provide the desired size -- but the Cycle cannot be truncated to
279 a size smaller than the largest element that is out of place:
281 >>> b = Cycle(2, 4)(1, 2)(3, 1, 4)(1, 3)
282 >>> b.list()
283 [0, 2, 1, 3, 4]
284 >>> b.list(b.size + 1)
285 [0, 2, 1, 3, 4, 5]
286 >>> b.list(-1)
287 [0, 2, 1]
289 Singletons are not shown when printing with one exception: the largest
290 element is always shown -- as a singleton if necessary:
292 >>> Cycle(1, 4, 10)(4, 5)
293 (1 5 4 10)
294 >>> Cycle(1, 2)(4)(5)(10)
295 (1 2)(10)
297 The array form can be used to instantiate a Permutation so other
298 properties of the permutation can be investigated:
300 >>> Perm(Cycle(1, 2)(3, 4).list()).transpositions()
301 [(1, 2), (3, 4)]
303 Notes
304 =====
306 The underlying structure of the Cycle is a dictionary and although
307 the __iter__ method has been redefined to give the array form of the
308 cycle, the underlying dictionary items are still available with the
309 such methods as items():
311 >>> list(Cycle(1, 2).items())
312 [(1, 2), (2, 1)]
314 See Also
315 ========
317 Permutation
318 """
319 def __missing__(self, arg):
320 """Enter arg into dictionary and return arg."""
321 return as_int(arg)
323 def __iter__(self):
324 yield from self.list()
326 def __call__(self, *other):
327 """Return product of cycles processed from R to L.
329 Examples
330 ========
332 >>> from sympy.combinatorics import Cycle
333 >>> Cycle(1, 2)(2, 3)
334 (1 3 2)
336 An instance of a Cycle will automatically parse list-like
337 objects and Permutations that are on the right. It is more
338 flexible than the Permutation in that all elements need not
339 be present:
341 >>> a = Cycle(1, 2)
342 >>> a(2, 3)
343 (1 3 2)
344 >>> a(2, 3)(4, 5)
345 (1 3 2)(4 5)
347 """
348 rv = Cycle(*other)
349 for k, v in zip(list(self.keys()), [rv[self[k]] for k in self.keys()]):
350 rv[k] = v
351 return rv
353 def list(self, size=None):
354 """Return the cycles as an explicit list starting from 0 up
355 to the greater of the largest value in the cycles and size.
357 Truncation of trailing unmoved items will occur when size
358 is less than the maximum element in the cycle; if this is
359 desired, setting ``size=-1`` will guarantee such trimming.
361 Examples
362 ========
364 >>> from sympy.combinatorics import Cycle
365 >>> p = Cycle(2, 3)(4, 5)
366 >>> p.list()
367 [0, 1, 3, 2, 5, 4]
368 >>> p.list(10)
369 [0, 1, 3, 2, 5, 4, 6, 7, 8, 9]
371 Passing a length too small will trim trailing, unchanged elements
372 in the permutation:
374 >>> Cycle(2, 4)(1, 2, 4).list(-1)
375 [0, 2, 1]
376 """
377 if not self and size is None:
378 raise ValueError('must give size for empty Cycle')
379 if size is not None:
380 big = max([i for i in self.keys() if self[i] != i] + [0])
381 size = max(size, big + 1)
382 else:
383 size = self.size
384 return [self[i] for i in range(size)]
386 def __repr__(self):
387 """We want it to print as a Cycle, not as a dict.
389 Examples
390 ========
392 >>> from sympy.combinatorics import Cycle
393 >>> Cycle(1, 2)
394 (1 2)
395 >>> print(_)
396 (1 2)
397 >>> list(Cycle(1, 2).items())
398 [(1, 2), (2, 1)]
399 """
400 if not self:
401 return 'Cycle()'
402 cycles = Permutation(self).cyclic_form
403 s = ''.join(str(tuple(c)) for c in cycles)
404 big = self.size - 1
405 if not any(i == big for c in cycles for i in c):
406 s += '(%s)' % big
407 return 'Cycle%s' % s
409 def __str__(self):
410 """We want it to be printed in a Cycle notation with no
411 comma in-between.
413 Examples
414 ========
416 >>> from sympy.combinatorics import Cycle
417 >>> Cycle(1, 2)
418 (1 2)
419 >>> Cycle(1, 2, 4)(5, 6)
420 (1 2 4)(5 6)
421 """
422 if not self:
423 return '()'
424 cycles = Permutation(self).cyclic_form
425 s = ''.join(str(tuple(c)) for c in cycles)
426 big = self.size - 1
427 if not any(i == big for c in cycles for i in c):
428 s += '(%s)' % big
429 s = s.replace(',', '')
430 return s
432 def __init__(self, *args):
433 """Load up a Cycle instance with the values for the cycle.
435 Examples
436 ========
438 >>> from sympy.combinatorics import Cycle
439 >>> Cycle(1, 2, 6)
440 (1 2 6)
441 """
443 if not args:
444 return
445 if len(args) == 1:
446 if isinstance(args[0], Permutation):
447 for c in args[0].cyclic_form:
448 self.update(self(*c))
449 return
450 elif isinstance(args[0], Cycle):
451 for k, v in args[0].items():
452 self[k] = v
453 return
454 args = [as_int(a) for a in args]
455 if any(i < 0 for i in args):
456 raise ValueError('negative integers are not allowed in a cycle.')
457 if has_dups(args):
458 raise ValueError('All elements must be unique in a cycle.')
459 for i in range(-len(args), 0):
460 self[args[i]] = args[i + 1]
462 @property
463 def size(self):
464 if not self:
465 return 0
466 return max(self.keys()) + 1
468 def copy(self):
469 return Cycle(self)
472class Permutation(Atom):
473 r"""
474 A permutation, alternatively known as an 'arrangement number' or 'ordering'
475 is an arrangement of the elements of an ordered list into a one-to-one
476 mapping with itself. The permutation of a given arrangement is given by
477 indicating the positions of the elements after re-arrangement [2]_. For
478 example, if one started with elements ``[x, y, a, b]`` (in that order) and
479 they were reordered as ``[x, y, b, a]`` then the permutation would be
480 ``[0, 1, 3, 2]``. Notice that (in SymPy) the first element is always referred
481 to as 0 and the permutation uses the indices of the elements in the
482 original ordering, not the elements ``(a, b, ...)`` themselves.
484 >>> from sympy.combinatorics import Permutation
485 >>> from sympy import init_printing
486 >>> init_printing(perm_cyclic=False, pretty_print=False)
488 Permutations Notation
489 =====================
491 Permutations are commonly represented in disjoint cycle or array forms.
493 Array Notation and 2-line Form
494 ------------------------------------
496 In the 2-line form, the elements and their final positions are shown
497 as a matrix with 2 rows:
499 [0 1 2 ... n-1]
500 [p(0) p(1) p(2) ... p(n-1)]
502 Since the first line is always ``range(n)``, where n is the size of p,
503 it is sufficient to represent the permutation by the second line,
504 referred to as the "array form" of the permutation. This is entered
505 in brackets as the argument to the Permutation class:
507 >>> p = Permutation([0, 2, 1]); p
508 Permutation([0, 2, 1])
510 Given i in range(p.size), the permutation maps i to i^p
512 >>> [i^p for i in range(p.size)]
513 [0, 2, 1]
515 The composite of two permutations p*q means first apply p, then q, so
516 i^(p*q) = (i^p)^q which is i^p^q according to Python precedence rules:
518 >>> q = Permutation([2, 1, 0])
519 >>> [i^p^q for i in range(3)]
520 [2, 0, 1]
521 >>> [i^(p*q) for i in range(3)]
522 [2, 0, 1]
524 One can use also the notation p(i) = i^p, but then the composition
525 rule is (p*q)(i) = q(p(i)), not p(q(i)):
527 >>> [(p*q)(i) for i in range(p.size)]
528 [2, 0, 1]
529 >>> [q(p(i)) for i in range(p.size)]
530 [2, 0, 1]
531 >>> [p(q(i)) for i in range(p.size)]
532 [1, 2, 0]
534 Disjoint Cycle Notation
535 -----------------------
537 In disjoint cycle notation, only the elements that have shifted are
538 indicated.
540 For example, [1, 3, 2, 0] can be represented as (0, 1, 3)(2).
541 This can be understood from the 2 line format of the given permutation.
542 In the 2-line form,
543 [0 1 2 3]
544 [1 3 2 0]
546 The element in the 0th position is 1, so 0 -> 1. The element in the 1st
547 position is three, so 1 -> 3. And the element in the third position is again
548 0, so 3 -> 0. Thus, 0 -> 1 -> 3 -> 0, and 2 -> 2. Thus, this can be represented
549 as 2 cycles: (0, 1, 3)(2).
550 In common notation, singular cycles are not explicitly written as they can be
551 inferred implicitly.
553 Only the relative ordering of elements in a cycle matter:
555 >>> Permutation(1,2,3) == Permutation(2,3,1) == Permutation(3,1,2)
556 True
558 The disjoint cycle notation is convenient when representing
559 permutations that have several cycles in them:
561 >>> Permutation(1, 2)(3, 5) == Permutation([[1, 2], [3, 5]])
562 True
564 It also provides some economy in entry when computing products of
565 permutations that are written in disjoint cycle notation:
567 >>> Permutation(1, 2)(1, 3)(2, 3)
568 Permutation([0, 3, 2, 1])
569 >>> _ == Permutation([[1, 2]])*Permutation([[1, 3]])*Permutation([[2, 3]])
570 True
572 Caution: when the cycles have common elements between them then the order
573 in which the permutations are applied matters. This module applies
574 the permutations from *left to right*.
576 >>> Permutation(1, 2)(2, 3) == Permutation([(1, 2), (2, 3)])
577 True
578 >>> Permutation(1, 2)(2, 3).list()
579 [0, 3, 1, 2]
581 In the above case, (1,2) is computed before (2,3).
582 As 0 -> 0, 0 -> 0, element in position 0 is 0.
583 As 1 -> 2, 2 -> 3, element in position 1 is 3.
584 As 2 -> 1, 1 -> 1, element in position 2 is 1.
585 As 3 -> 3, 3 -> 2, element in position 3 is 2.
587 If the first and second elements had been
588 swapped first, followed by the swapping of the second
589 and third, the result would have been [0, 2, 3, 1].
590 If, you want to apply the cycles in the conventional
591 right to left order, call the function with arguments in reverse order
592 as demonstrated below:
594 >>> Permutation([(1, 2), (2, 3)][::-1]).list()
595 [0, 2, 3, 1]
597 Entering a singleton in a permutation is a way to indicate the size of the
598 permutation. The ``size`` keyword can also be used.
600 Array-form entry:
602 >>> Permutation([[1, 2], [9]])
603 Permutation([0, 2, 1], size=10)
604 >>> Permutation([[1, 2]], size=10)
605 Permutation([0, 2, 1], size=10)
607 Cyclic-form entry:
609 >>> Permutation(1, 2, size=10)
610 Permutation([0, 2, 1], size=10)
611 >>> Permutation(9)(1, 2)
612 Permutation([0, 2, 1], size=10)
614 Caution: no singleton containing an element larger than the largest
615 in any previous cycle can be entered. This is an important difference
616 in how Permutation and Cycle handle the ``__call__`` syntax. A singleton
617 argument at the start of a Permutation performs instantiation of the
618 Permutation and is permitted:
620 >>> Permutation(5)
621 Permutation([], size=6)
623 A singleton entered after instantiation is a call to the permutation
624 -- a function call -- and if the argument is out of range it will
625 trigger an error. For this reason, it is better to start the cycle
626 with the singleton:
628 The following fails because there is no element 3:
630 >>> Permutation(1, 2)(3)
631 Traceback (most recent call last):
632 ...
633 IndexError: list index out of range
635 This is ok: only the call to an out of range singleton is prohibited;
636 otherwise the permutation autosizes:
638 >>> Permutation(3)(1, 2)
639 Permutation([0, 2, 1, 3])
640 >>> Permutation(1, 2)(3, 4) == Permutation(3, 4)(1, 2)
641 True
644 Equality testing
645 ----------------
647 The array forms must be the same in order for permutations to be equal:
649 >>> Permutation([1, 0, 2, 3]) == Permutation([1, 0])
650 False
653 Identity Permutation
654 --------------------
656 The identity permutation is a permutation in which no element is out of
657 place. It can be entered in a variety of ways. All the following create
658 an identity permutation of size 4:
660 >>> I = Permutation([0, 1, 2, 3])
661 >>> all(p == I for p in [
662 ... Permutation(3),
663 ... Permutation(range(4)),
664 ... Permutation([], size=4),
665 ... Permutation(size=4)])
666 True
668 Watch out for entering the range *inside* a set of brackets (which is
669 cycle notation):
671 >>> I == Permutation([range(4)])
672 False
675 Permutation Printing
676 ====================
678 There are a few things to note about how Permutations are printed.
680 .. deprecated:: 1.6
682 Configuring Permutation printing by setting
683 ``Permutation.print_cyclic`` is deprecated. Users should use the
684 ``perm_cyclic`` flag to the printers, as described below.
686 1) If you prefer one form (array or cycle) over another, you can set
687 ``init_printing`` with the ``perm_cyclic`` flag.
689 >>> from sympy import init_printing
690 >>> p = Permutation(1, 2)(4, 5)(3, 4)
691 >>> p
692 Permutation([0, 2, 1, 4, 5, 3])
694 >>> init_printing(perm_cyclic=True, pretty_print=False)
695 >>> p
696 (1 2)(3 4 5)
698 2) Regardless of the setting, a list of elements in the array for cyclic
699 form can be obtained and either of those can be copied and supplied as
700 the argument to Permutation:
702 >>> p.array_form
703 [0, 2, 1, 4, 5, 3]
704 >>> p.cyclic_form
705 [[1, 2], [3, 4, 5]]
706 >>> Permutation(_) == p
707 True
709 3) Printing is economical in that as little as possible is printed while
710 retaining all information about the size of the permutation:
712 >>> init_printing(perm_cyclic=False, pretty_print=False)
713 >>> Permutation([1, 0, 2, 3])
714 Permutation([1, 0, 2, 3])
715 >>> Permutation([1, 0, 2, 3], size=20)
716 Permutation([1, 0], size=20)
717 >>> Permutation([1, 0, 2, 4, 3, 5, 6], size=20)
718 Permutation([1, 0, 2, 4, 3], size=20)
720 >>> p = Permutation([1, 0, 2, 3])
721 >>> init_printing(perm_cyclic=True, pretty_print=False)
722 >>> p
723 (3)(0 1)
724 >>> init_printing(perm_cyclic=False, pretty_print=False)
726 The 2 was not printed but it is still there as can be seen with the
727 array_form and size methods:
729 >>> p.array_form
730 [1, 0, 2, 3]
731 >>> p.size
732 4
734 Short introduction to other methods
735 ===================================
737 The permutation can act as a bijective function, telling what element is
738 located at a given position
740 >>> q = Permutation([5, 2, 3, 4, 1, 0])
741 >>> q.array_form[1] # the hard way
742 2
743 >>> q(1) # the easy way
744 2
745 >>> {i: q(i) for i in range(q.size)} # showing the bijection
746 {0: 5, 1: 2, 2: 3, 3: 4, 4: 1, 5: 0}
748 The full cyclic form (including singletons) can be obtained:
750 >>> p.full_cyclic_form
751 [[0, 1], [2], [3]]
753 Any permutation can be factored into transpositions of pairs of elements:
755 >>> Permutation([[1, 2], [3, 4, 5]]).transpositions()
756 [(1, 2), (3, 5), (3, 4)]
757 >>> Permutation.rmul(*[Permutation([ti], size=6) for ti in _]).cyclic_form
758 [[1, 2], [3, 4, 5]]
760 The number of permutations on a set of n elements is given by n! and is
761 called the cardinality.
763 >>> p.size
764 4
765 >>> p.cardinality
766 24
768 A given permutation has a rank among all the possible permutations of the
769 same elements, but what that rank is depends on how the permutations are
770 enumerated. (There are a number of different methods of doing so.) The
771 lexicographic rank is given by the rank method and this rank is used to
772 increment a permutation with addition/subtraction:
774 >>> p.rank()
775 6
776 >>> p + 1
777 Permutation([1, 0, 3, 2])
778 >>> p.next_lex()
779 Permutation([1, 0, 3, 2])
780 >>> _.rank()
781 7
782 >>> p.unrank_lex(p.size, rank=7)
783 Permutation([1, 0, 3, 2])
785 The product of two permutations p and q is defined as their composition as
786 functions, (p*q)(i) = q(p(i)) [6]_.
788 >>> p = Permutation([1, 0, 2, 3])
789 >>> q = Permutation([2, 3, 1, 0])
790 >>> list(q*p)
791 [2, 3, 0, 1]
792 >>> list(p*q)
793 [3, 2, 1, 0]
794 >>> [q(p(i)) for i in range(p.size)]
795 [3, 2, 1, 0]
797 The permutation can be 'applied' to any list-like object, not only
798 Permutations:
800 >>> p(['zero', 'one', 'four', 'two'])
801 ['one', 'zero', 'four', 'two']
802 >>> p('zo42')
803 ['o', 'z', '4', '2']
805 If you have a list of arbitrary elements, the corresponding permutation
806 can be found with the from_sequence method:
808 >>> Permutation.from_sequence('SymPy')
809 Permutation([1, 3, 2, 0, 4])
811 Checking if a Permutation is contained in a Group
812 =================================================
814 Generally if you have a group of permutations G on n symbols, and
815 you're checking if a permutation on less than n symbols is part
816 of that group, the check will fail.
818 Here is an example for n=5 and we check if the cycle
819 (1,2,3) is in G:
821 >>> from sympy import init_printing
822 >>> init_printing(perm_cyclic=True, pretty_print=False)
823 >>> from sympy.combinatorics import Cycle, Permutation
824 >>> from sympy.combinatorics.perm_groups import PermutationGroup
825 >>> G = PermutationGroup(Cycle(2, 3)(4, 5), Cycle(1, 2, 3, 4, 5))
826 >>> p1 = Permutation(Cycle(2, 5, 3))
827 >>> p2 = Permutation(Cycle(1, 2, 3))
828 >>> a1 = Permutation(Cycle(1, 2, 3).list(6))
829 >>> a2 = Permutation(Cycle(1, 2, 3)(5))
830 >>> a3 = Permutation(Cycle(1, 2, 3),size=6)
831 >>> for p in [p1,p2,a1,a2,a3]: p, G.contains(p)
832 ((2 5 3), True)
833 ((1 2 3), False)
834 ((5)(1 2 3), True)
835 ((5)(1 2 3), True)
836 ((5)(1 2 3), True)
838 The check for p2 above will fail.
840 Checking if p1 is in G works because SymPy knows
841 G is a group on 5 symbols, and p1 is also on 5 symbols
842 (its largest element is 5).
844 For ``a1``, the ``.list(6)`` call will extend the permutation to 5
845 symbols, so the test will work as well. In the case of ``a2`` the
846 permutation is being extended to 5 symbols by using a singleton,
847 and in the case of ``a3`` it's extended through the constructor
848 argument ``size=6``.
850 There is another way to do this, which is to tell the ``contains``
851 method that the number of symbols the group is on does not need to
852 match perfectly the number of symbols for the permutation:
854 >>> G.contains(p2,strict=False)
855 True
857 This can be via the ``strict`` argument to the ``contains`` method,
858 and SymPy will try to extend the permutation on its own and then
859 perform the containment check.
861 See Also
862 ========
864 Cycle
866 References
867 ==========
869 .. [1] Skiena, S. 'Permutations.' 1.1 in Implementing Discrete Mathematics
870 Combinatorics and Graph Theory with Mathematica. Reading, MA:
871 Addison-Wesley, pp. 3-16, 1990.
873 .. [2] Knuth, D. E. The Art of Computer Programming, Vol. 4: Combinatorial
874 Algorithms, 1st ed. Reading, MA: Addison-Wesley, 2011.
876 .. [3] Wendy Myrvold and Frank Ruskey. 2001. Ranking and unranking
877 permutations in linear time. Inf. Process. Lett. 79, 6 (September 2001),
878 281-284. DOI=10.1016/S0020-0190(01)00141-7
880 .. [4] D. L. Kreher, D. R. Stinson 'Combinatorial Algorithms'
881 CRC Press, 1999
883 .. [5] Graham, R. L.; Knuth, D. E.; and Patashnik, O.
884 Concrete Mathematics: A Foundation for Computer Science, 2nd ed.
885 Reading, MA: Addison-Wesley, 1994.
887 .. [6] https://en.wikipedia.org/w/index.php?oldid=499948155#Product_and_inverse
889 .. [7] https://en.wikipedia.org/wiki/Lehmer_code
891 """
893 is_Permutation = True
895 _array_form = None
896 _cyclic_form = None
897 _cycle_structure = None
898 _size = None
899 _rank = None
901 def __new__(cls, *args, size=None, **kwargs):
902 """
903 Constructor for the Permutation object from a list or a
904 list of lists in which all elements of the permutation may
905 appear only once.
907 Examples
908 ========
910 >>> from sympy.combinatorics import Permutation
911 >>> from sympy import init_printing
912 >>> init_printing(perm_cyclic=False, pretty_print=False)
914 Permutations entered in array-form are left unaltered:
916 >>> Permutation([0, 2, 1])
917 Permutation([0, 2, 1])
919 Permutations entered in cyclic form are converted to array form;
920 singletons need not be entered, but can be entered to indicate the
921 largest element:
923 >>> Permutation([[4, 5, 6], [0, 1]])
924 Permutation([1, 0, 2, 3, 5, 6, 4])
925 >>> Permutation([[4, 5, 6], [0, 1], [19]])
926 Permutation([1, 0, 2, 3, 5, 6, 4], size=20)
928 All manipulation of permutations assumes that the smallest element
929 is 0 (in keeping with 0-based indexing in Python) so if the 0 is
930 missing when entering a permutation in array form, an error will be
931 raised:
933 >>> Permutation([2, 1])
934 Traceback (most recent call last):
935 ...
936 ValueError: Integers 0 through 2 must be present.
938 If a permutation is entered in cyclic form, it can be entered without
939 singletons and the ``size`` specified so those values can be filled
940 in, otherwise the array form will only extend to the maximum value
941 in the cycles:
943 >>> Permutation([[1, 4], [3, 5, 2]], size=10)
944 Permutation([0, 4, 3, 5, 1, 2], size=10)
945 >>> _.array_form
946 [0, 4, 3, 5, 1, 2, 6, 7, 8, 9]
947 """
948 if size is not None:
949 size = int(size)
951 #a) ()
952 #b) (1) = identity
953 #c) (1, 2) = cycle
954 #d) ([1, 2, 3]) = array form
955 #e) ([[1, 2]]) = cyclic form
956 #f) (Cycle) = conversion to permutation
957 #g) (Permutation) = adjust size or return copy
958 ok = True
959 if not args: # a
960 return cls._af_new(list(range(size or 0)))
961 elif len(args) > 1: # c
962 return cls._af_new(Cycle(*args).list(size))
963 if len(args) == 1:
964 a = args[0]
965 if isinstance(a, cls): # g
966 if size is None or size == a.size:
967 return a
968 return cls(a.array_form, size=size)
969 if isinstance(a, Cycle): # f
970 return cls._af_new(a.list(size))
971 if not is_sequence(a): # b
972 if size is not None and a + 1 > size:
973 raise ValueError('size is too small when max is %s' % a)
974 return cls._af_new(list(range(a + 1)))
975 if has_variety(is_sequence(ai) for ai in a):
976 ok = False
977 else:
978 ok = False
979 if not ok:
980 raise ValueError("Permutation argument must be a list of ints, "
981 "a list of lists, Permutation or Cycle.")
983 # safe to assume args are valid; this also makes a copy
984 # of the args
985 args = list(args[0])
987 is_cycle = args and is_sequence(args[0])
988 if is_cycle: # e
989 args = [[int(i) for i in c] for c in args]
990 else: # d
991 args = [int(i) for i in args]
993 # if there are n elements present, 0, 1, ..., n-1 should be present
994 # unless a cycle notation has been provided. A 0 will be added
995 # for convenience in case one wants to enter permutations where
996 # counting starts from 1.
998 temp = flatten(args)
999 if has_dups(temp) and not is_cycle:
1000 raise ValueError('there were repeated elements.')
1001 temp = set(temp)
1003 if not is_cycle:
1004 if temp != set(range(len(temp))):
1005 raise ValueError('Integers 0 through %s must be present.' %
1006 max(temp))
1007 if size is not None and temp and max(temp) + 1 > size:
1008 raise ValueError('max element should not exceed %s' % (size - 1))
1010 if is_cycle:
1011 # it's not necessarily canonical so we won't store
1012 # it -- use the array form instead
1013 c = Cycle()
1014 for ci in args:
1015 c = c(*ci)
1016 aform = c.list()
1017 else:
1018 aform = list(args)
1019 if size and size > len(aform):
1020 # don't allow for truncation of permutation which
1021 # might split a cycle and lead to an invalid aform
1022 # but do allow the permutation size to be increased
1023 aform.extend(list(range(len(aform), size)))
1025 return cls._af_new(aform)
1027 @classmethod
1028 def _af_new(cls, perm):
1029 """A method to produce a Permutation object from a list;
1030 the list is bound to the _array_form attribute, so it must
1031 not be modified; this method is meant for internal use only;
1032 the list ``a`` is supposed to be generated as a temporary value
1033 in a method, so p = Perm._af_new(a) is the only object
1034 to hold a reference to ``a``::
1036 Examples
1037 ========
1039 >>> from sympy.combinatorics.permutations import Perm
1040 >>> from sympy import init_printing
1041 >>> init_printing(perm_cyclic=False, pretty_print=False)
1042 >>> a = [2, 1, 3, 0]
1043 >>> p = Perm._af_new(a)
1044 >>> p
1045 Permutation([2, 1, 3, 0])
1047 """
1048 p = super().__new__(cls)
1049 p._array_form = perm
1050 p._size = len(perm)
1051 return p
1053 def _hashable_content(self):
1054 # the array_form (a list) is the Permutation arg, so we need to
1055 # return a tuple, instead
1056 return tuple(self.array_form)
1058 @property
1059 def array_form(self):
1060 """
1061 Return a copy of the attribute _array_form
1062 Examples
1063 ========
1065 >>> from sympy.combinatorics import Permutation
1066 >>> p = Permutation([[2, 0], [3, 1]])
1067 >>> p.array_form
1068 [2, 3, 0, 1]
1069 >>> Permutation([[2, 0, 3, 1]]).array_form
1070 [3, 2, 0, 1]
1071 >>> Permutation([2, 0, 3, 1]).array_form
1072 [2, 0, 3, 1]
1073 >>> Permutation([[1, 2], [4, 5]]).array_form
1074 [0, 2, 1, 3, 5, 4]
1075 """
1076 return self._array_form[:]
1078 def list(self, size=None):
1079 """Return the permutation as an explicit list, possibly
1080 trimming unmoved elements if size is less than the maximum
1081 element in the permutation; if this is desired, setting
1082 ``size=-1`` will guarantee such trimming.
1084 Examples
1085 ========
1087 >>> from sympy.combinatorics import Permutation
1088 >>> p = Permutation(2, 3)(4, 5)
1089 >>> p.list()
1090 [0, 1, 3, 2, 5, 4]
1091 >>> p.list(10)
1092 [0, 1, 3, 2, 5, 4, 6, 7, 8, 9]
1094 Passing a length too small will trim trailing, unchanged elements
1095 in the permutation:
1097 >>> Permutation(2, 4)(1, 2, 4).list(-1)
1098 [0, 2, 1]
1099 >>> Permutation(3).list(-1)
1100 []
1101 """
1102 if not self and size is None:
1103 raise ValueError('must give size for empty Cycle')
1104 rv = self.array_form
1105 if size is not None:
1106 if size > self.size:
1107 rv.extend(list(range(self.size, size)))
1108 else:
1109 # find first value from rhs where rv[i] != i
1110 i = self.size - 1
1111 while rv:
1112 if rv[-1] != i:
1113 break
1114 rv.pop()
1115 i -= 1
1116 return rv
1118 @property
1119 def cyclic_form(self):
1120 """
1121 This is used to convert to the cyclic notation
1122 from the canonical notation. Singletons are omitted.
1124 Examples
1125 ========
1127 >>> from sympy.combinatorics import Permutation
1128 >>> p = Permutation([0, 3, 1, 2])
1129 >>> p.cyclic_form
1130 [[1, 3, 2]]
1131 >>> Permutation([1, 0, 2, 4, 3, 5]).cyclic_form
1132 [[0, 1], [3, 4]]
1134 See Also
1135 ========
1137 array_form, full_cyclic_form
1138 """
1139 if self._cyclic_form is not None:
1140 return list(self._cyclic_form)
1141 array_form = self.array_form
1142 unchecked = [True] * len(array_form)
1143 cyclic_form = []
1144 for i in range(len(array_form)):
1145 if unchecked[i]:
1146 cycle = []
1147 cycle.append(i)
1148 unchecked[i] = False
1149 j = i
1150 while unchecked[array_form[j]]:
1151 j = array_form[j]
1152 cycle.append(j)
1153 unchecked[j] = False
1154 if len(cycle) > 1:
1155 cyclic_form.append(cycle)
1156 assert cycle == list(minlex(cycle))
1157 cyclic_form.sort()
1158 self._cyclic_form = cyclic_form[:]
1159 return cyclic_form
1161 @property
1162 def full_cyclic_form(self):
1163 """Return permutation in cyclic form including singletons.
1165 Examples
1166 ========
1168 >>> from sympy.combinatorics import Permutation
1169 >>> Permutation([0, 2, 1]).full_cyclic_form
1170 [[0], [1, 2]]
1171 """
1172 need = set(range(self.size)) - set(flatten(self.cyclic_form))
1173 rv = self.cyclic_form + [[i] for i in need]
1174 rv.sort()
1175 return rv
1177 @property
1178 def size(self):
1179 """
1180 Returns the number of elements in the permutation.
1182 Examples
1183 ========
1185 >>> from sympy.combinatorics import Permutation
1186 >>> Permutation([[3, 2], [0, 1]]).size
1187 4
1189 See Also
1190 ========
1192 cardinality, length, order, rank
1193 """
1194 return self._size
1196 def support(self):
1197 """Return the elements in permutation, P, for which P[i] != i.
1199 Examples
1200 ========
1202 >>> from sympy.combinatorics import Permutation
1203 >>> p = Permutation([[3, 2], [0, 1], [4]])
1204 >>> p.array_form
1205 [1, 0, 3, 2, 4]
1206 >>> p.support()
1207 [0, 1, 2, 3]
1208 """
1209 a = self.array_form
1210 return [i for i, e in enumerate(a) if a[i] != i]
1212 def __add__(self, other):
1213 """Return permutation that is other higher in rank than self.
1215 The rank is the lexicographical rank, with the identity permutation
1216 having rank of 0.
1218 Examples
1219 ========
1221 >>> from sympy.combinatorics import Permutation
1222 >>> I = Permutation([0, 1, 2, 3])
1223 >>> a = Permutation([2, 1, 3, 0])
1224 >>> I + a.rank() == a
1225 True
1227 See Also
1228 ========
1230 __sub__, inversion_vector
1232 """
1233 rank = (self.rank() + other) % self.cardinality
1234 rv = self.unrank_lex(self.size, rank)
1235 rv._rank = rank
1236 return rv
1238 def __sub__(self, other):
1239 """Return the permutation that is other lower in rank than self.
1241 See Also
1242 ========
1244 __add__
1245 """
1246 return self.__add__(-other)
1248 @staticmethod
1249 def rmul(*args):
1250 """
1251 Return product of Permutations [a, b, c, ...] as the Permutation whose
1252 ith value is a(b(c(i))).
1254 a, b, c, ... can be Permutation objects or tuples.
1256 Examples
1257 ========
1259 >>> from sympy.combinatorics import Permutation
1261 >>> a, b = [1, 0, 2], [0, 2, 1]
1262 >>> a = Permutation(a); b = Permutation(b)
1263 >>> list(Permutation.rmul(a, b))
1264 [1, 2, 0]
1265 >>> [a(b(i)) for i in range(3)]
1266 [1, 2, 0]
1268 This handles the operands in reverse order compared to the ``*`` operator:
1270 >>> a = Permutation(a); b = Permutation(b)
1271 >>> list(a*b)
1272 [2, 0, 1]
1273 >>> [b(a(i)) for i in range(3)]
1274 [2, 0, 1]
1276 Notes
1277 =====
1279 All items in the sequence will be parsed by Permutation as
1280 necessary as long as the first item is a Permutation:
1282 >>> Permutation.rmul(a, [0, 2, 1]) == Permutation.rmul(a, b)
1283 True
1285 The reverse order of arguments will raise a TypeError.
1287 """
1288 rv = args[0]
1289 for i in range(1, len(args)):
1290 rv = args[i]*rv
1291 return rv
1293 @classmethod
1294 def rmul_with_af(cls, *args):
1295 """
1296 same as rmul, but the elements of args are Permutation objects
1297 which have _array_form
1298 """
1299 a = [x._array_form for x in args]
1300 rv = cls._af_new(_af_rmuln(*a))
1301 return rv
1303 def mul_inv(self, other):
1304 """
1305 other*~self, self and other have _array_form
1306 """
1307 a = _af_invert(self._array_form)
1308 b = other._array_form
1309 return self._af_new(_af_rmul(a, b))
1311 def __rmul__(self, other):
1312 """This is needed to coerce other to Permutation in rmul."""
1313 cls = type(self)
1314 return cls(other)*self
1316 def __mul__(self, other):
1317 """
1318 Return the product a*b as a Permutation; the ith value is b(a(i)).
1320 Examples
1321 ========
1323 >>> from sympy.combinatorics.permutations import _af_rmul, Permutation
1325 >>> a, b = [1, 0, 2], [0, 2, 1]
1326 >>> a = Permutation(a); b = Permutation(b)
1327 >>> list(a*b)
1328 [2, 0, 1]
1329 >>> [b(a(i)) for i in range(3)]
1330 [2, 0, 1]
1332 This handles operands in reverse order compared to _af_rmul and rmul:
1334 >>> al = list(a); bl = list(b)
1335 >>> _af_rmul(al, bl)
1336 [1, 2, 0]
1337 >>> [al[bl[i]] for i in range(3)]
1338 [1, 2, 0]
1340 It is acceptable for the arrays to have different lengths; the shorter
1341 one will be padded to match the longer one:
1343 >>> from sympy import init_printing
1344 >>> init_printing(perm_cyclic=False, pretty_print=False)
1345 >>> b*Permutation([1, 0])
1346 Permutation([1, 2, 0])
1347 >>> Permutation([1, 0])*b
1348 Permutation([2, 0, 1])
1350 It is also acceptable to allow coercion to handle conversion of a
1351 single list to the left of a Permutation:
1353 >>> [0, 1]*a # no change: 2-element identity
1354 Permutation([1, 0, 2])
1355 >>> [[0, 1]]*a # exchange first two elements
1356 Permutation([0, 1, 2])
1358 You cannot use more than 1 cycle notation in a product of cycles
1359 since coercion can only handle one argument to the left. To handle
1360 multiple cycles it is convenient to use Cycle instead of Permutation:
1362 >>> [[1, 2]]*[[2, 3]]*Permutation([]) # doctest: +SKIP
1363 >>> from sympy.combinatorics.permutations import Cycle
1364 >>> Cycle(1, 2)(2, 3)
1365 (1 3 2)
1367 """
1368 from sympy.combinatorics.perm_groups import PermutationGroup, Coset
1369 if isinstance(other, PermutationGroup):
1370 return Coset(self, other, dir='-')
1371 a = self.array_form
1372 # __rmul__ makes sure the other is a Permutation
1373 b = other.array_form
1374 if not b:
1375 perm = a
1376 else:
1377 b.extend(list(range(len(b), len(a))))
1378 perm = [b[i] for i in a] + b[len(a):]
1379 return self._af_new(perm)
1381 def commutes_with(self, other):
1382 """
1383 Checks if the elements are commuting.
1385 Examples
1386 ========
1388 >>> from sympy.combinatorics import Permutation
1389 >>> a = Permutation([1, 4, 3, 0, 2, 5])
1390 >>> b = Permutation([0, 1, 2, 3, 4, 5])
1391 >>> a.commutes_with(b)
1392 True
1393 >>> b = Permutation([2, 3, 5, 4, 1, 0])
1394 >>> a.commutes_with(b)
1395 False
1396 """
1397 a = self.array_form
1398 b = other.array_form
1399 return _af_commutes_with(a, b)
1401 def __pow__(self, n):
1402 """
1403 Routine for finding powers of a permutation.
1405 Examples
1406 ========
1408 >>> from sympy.combinatorics import Permutation
1409 >>> from sympy import init_printing
1410 >>> init_printing(perm_cyclic=False, pretty_print=False)
1411 >>> p = Permutation([2, 0, 3, 1])
1412 >>> p.order()
1413 4
1414 >>> p**4
1415 Permutation([0, 1, 2, 3])
1416 """
1417 if isinstance(n, Permutation):
1418 raise NotImplementedError(
1419 'p**p is not defined; do you mean p^p (conjugate)?')
1420 n = int(n)
1421 return self._af_new(_af_pow(self.array_form, n))
1423 def __rxor__(self, i):
1424 """Return self(i) when ``i`` is an int.
1426 Examples
1427 ========
1429 >>> from sympy.combinatorics import Permutation
1430 >>> p = Permutation(1, 2, 9)
1431 >>> 2^p == p(2) == 9
1432 True
1433 """
1434 if int(i) == i:
1435 return self(i)
1436 else:
1437 raise NotImplementedError(
1438 "i^p = p(i) when i is an integer, not %s." % i)
1440 def __xor__(self, h):
1441 """Return the conjugate permutation ``~h*self*h` `.
1443 Explanation
1444 ===========
1446 If ``a`` and ``b`` are conjugates, ``a = h*b*~h`` and
1447 ``b = ~h*a*h`` and both have the same cycle structure.
1449 Examples
1450 ========
1452 >>> from sympy.combinatorics import Permutation
1453 >>> p = Permutation(1, 2, 9)
1454 >>> q = Permutation(6, 9, 8)
1455 >>> p*q != q*p
1456 True
1458 Calculate and check properties of the conjugate:
1460 >>> c = p^q
1461 >>> c == ~q*p*q and p == q*c*~q
1462 True
1464 The expression q^p^r is equivalent to q^(p*r):
1466 >>> r = Permutation(9)(4, 6, 8)
1467 >>> q^p^r == q^(p*r)
1468 True
1470 If the term to the left of the conjugate operator, i, is an integer
1471 then this is interpreted as selecting the ith element from the
1472 permutation to the right:
1474 >>> all(i^p == p(i) for i in range(p.size))
1475 True
1477 Note that the * operator as higher precedence than the ^ operator:
1479 >>> q^r*p^r == q^(r*p)^r == Permutation(9)(1, 6, 4)
1480 True
1482 Notes
1483 =====
1485 In Python the precedence rule is p^q^r = (p^q)^r which differs
1486 in general from p^(q^r)
1488 >>> q^p^r
1489 (9)(1 4 8)
1490 >>> q^(p^r)
1491 (9)(1 8 6)
1493 For a given r and p, both of the following are conjugates of p:
1494 ~r*p*r and r*p*~r. But these are not necessarily the same:
1496 >>> ~r*p*r == r*p*~r
1497 True
1499 >>> p = Permutation(1, 2, 9)(5, 6)
1500 >>> ~r*p*r == r*p*~r
1501 False
1503 The conjugate ~r*p*r was chosen so that ``p^q^r`` would be equivalent
1504 to ``p^(q*r)`` rather than ``p^(r*q)``. To obtain r*p*~r, pass ~r to
1505 this method:
1507 >>> p^~r == r*p*~r
1508 True
1509 """
1511 if self.size != h.size:
1512 raise ValueError("The permutations must be of equal size.")
1513 a = [None]*self.size
1514 h = h._array_form
1515 p = self._array_form
1516 for i in range(self.size):
1517 a[h[i]] = h[p[i]]
1518 return self._af_new(a)
1520 def transpositions(self):
1521 """
1522 Return the permutation decomposed into a list of transpositions.
1524 Explanation
1525 ===========
1527 It is always possible to express a permutation as the product of
1528 transpositions, see [1]
1530 Examples
1531 ========
1533 >>> from sympy.combinatorics import Permutation
1534 >>> p = Permutation([[1, 2, 3], [0, 4, 5, 6, 7]])
1535 >>> t = p.transpositions()
1536 >>> t
1537 [(0, 7), (0, 6), (0, 5), (0, 4), (1, 3), (1, 2)]
1538 >>> print(''.join(str(c) for c in t))
1539 (0, 7)(0, 6)(0, 5)(0, 4)(1, 3)(1, 2)
1540 >>> Permutation.rmul(*[Permutation([ti], size=p.size) for ti in t]) == p
1541 True
1543 References
1544 ==========
1546 .. [1] https://en.wikipedia.org/wiki/Transposition_%28mathematics%29#Properties
1548 """
1549 a = self.cyclic_form
1550 res = []
1551 for x in a:
1552 nx = len(x)
1553 if nx == 2:
1554 res.append(tuple(x))
1555 elif nx > 2:
1556 first = x[0]
1557 for y in x[nx - 1:0:-1]:
1558 res.append((first, y))
1559 return res
1561 @classmethod
1562 def from_sequence(self, i, key=None):
1563 """Return the permutation needed to obtain ``i`` from the sorted
1564 elements of ``i``. If custom sorting is desired, a key can be given.
1566 Examples
1567 ========
1569 >>> from sympy.combinatorics import Permutation
1571 >>> Permutation.from_sequence('SymPy')
1572 (4)(0 1 3)
1573 >>> _(sorted("SymPy"))
1574 ['S', 'y', 'm', 'P', 'y']
1575 >>> Permutation.from_sequence('SymPy', key=lambda x: x.lower())
1576 (4)(0 2)(1 3)
1577 """
1578 ic = list(zip(i, list(range(len(i)))))
1579 if key:
1580 ic.sort(key=lambda x: key(x[0]))
1581 else:
1582 ic.sort()
1583 return ~Permutation([i[1] for i in ic])
1585 def __invert__(self):
1586 """
1587 Return the inverse of the permutation.
1589 A permutation multiplied by its inverse is the identity permutation.
1591 Examples
1592 ========
1594 >>> from sympy.combinatorics import Permutation
1595 >>> from sympy import init_printing
1596 >>> init_printing(perm_cyclic=False, pretty_print=False)
1597 >>> p = Permutation([[2, 0], [3, 1]])
1598 >>> ~p
1599 Permutation([2, 3, 0, 1])
1600 >>> _ == p**-1
1601 True
1602 >>> p*~p == ~p*p == Permutation([0, 1, 2, 3])
1603 True
1604 """
1605 return self._af_new(_af_invert(self._array_form))
1607 def __iter__(self):
1608 """Yield elements from array form.
1610 Examples
1611 ========
1613 >>> from sympy.combinatorics import Permutation
1614 >>> list(Permutation(range(3)))
1615 [0, 1, 2]
1616 """
1617 yield from self.array_form
1619 def __repr__(self):
1620 return srepr(self)
1622 def __call__(self, *i):
1623 """
1624 Allows applying a permutation instance as a bijective function.
1626 Examples
1627 ========
1629 >>> from sympy.combinatorics import Permutation
1630 >>> p = Permutation([[2, 0], [3, 1]])
1631 >>> p.array_form
1632 [2, 3, 0, 1]
1633 >>> [p(i) for i in range(4)]
1634 [2, 3, 0, 1]
1636 If an array is given then the permutation selects the items
1637 from the array (i.e. the permutation is applied to the array):
1639 >>> from sympy.abc import x
1640 >>> p([x, 1, 0, x**2])
1641 [0, x**2, x, 1]
1642 """
1643 # list indices can be Integer or int; leave this
1644 # as it is (don't test or convert it) because this
1645 # gets called a lot and should be fast
1646 if len(i) == 1:
1647 i = i[0]
1648 if not isinstance(i, Iterable):
1649 i = as_int(i)
1650 if i < 0 or i > self.size:
1651 raise TypeError(
1652 "{} should be an integer between 0 and {}"
1653 .format(i, self.size-1))
1654 return self._array_form[i]
1655 # P([a, b, c])
1656 if len(i) != self.size:
1657 raise TypeError(
1658 "{} should have the length {}.".format(i, self.size))
1659 return [i[j] for j in self._array_form]
1660 # P(1, 2, 3)
1661 return self*Permutation(Cycle(*i), size=self.size)
1663 def atoms(self):
1664 """
1665 Returns all the elements of a permutation
1667 Examples
1668 ========
1670 >>> from sympy.combinatorics import Permutation
1671 >>> Permutation([0, 1, 2, 3, 4, 5]).atoms()
1672 {0, 1, 2, 3, 4, 5}
1673 >>> Permutation([[0, 1], [2, 3], [4, 5]]).atoms()
1674 {0, 1, 2, 3, 4, 5}
1675 """
1676 return set(self.array_form)
1678 def apply(self, i):
1679 r"""Apply the permutation to an expression.
1681 Parameters
1682 ==========
1684 i : Expr
1685 It should be an integer between $0$ and $n-1$ where $n$
1686 is the size of the permutation.
1688 If it is a symbol or a symbolic expression that can
1689 have integer values, an ``AppliedPermutation`` object
1690 will be returned which can represent an unevaluated
1691 function.
1693 Notes
1694 =====
1696 Any permutation can be defined as a bijective function
1697 $\sigma : \{ 0, 1, \dots, n-1 \} \rightarrow \{ 0, 1, \dots, n-1 \}$
1698 where $n$ denotes the size of the permutation.
1700 The definition may even be extended for any set with distinctive
1701 elements, such that the permutation can even be applied for
1702 real numbers or such, however, it is not implemented for now for
1703 computational reasons and the integrity with the group theory
1704 module.
1706 This function is similar to the ``__call__`` magic, however,
1707 ``__call__`` magic already has some other applications like
1708 permuting an array or attaching new cycles, which would
1709 not always be mathematically consistent.
1711 This also guarantees that the return type is a SymPy integer,
1712 which guarantees the safety to use assumptions.
1713 """
1714 i = _sympify(i)
1715 if i.is_integer is False:
1716 raise NotImplementedError("{} should be an integer.".format(i))
1718 n = self.size
1719 if (i < 0) == True or (i >= n) == True:
1720 raise NotImplementedError(
1721 "{} should be an integer between 0 and {}".format(i, n-1))
1723 if i.is_Integer:
1724 return Integer(self._array_form[i])
1725 return AppliedPermutation(self, i)
1727 def next_lex(self):
1728 """
1729 Returns the next permutation in lexicographical order.
1730 If self is the last permutation in lexicographical order
1731 it returns None.
1732 See [4] section 2.4.
1735 Examples
1736 ========
1738 >>> from sympy.combinatorics import Permutation
1739 >>> p = Permutation([2, 3, 1, 0])
1740 >>> p = Permutation([2, 3, 1, 0]); p.rank()
1741 17
1742 >>> p = p.next_lex(); p.rank()
1743 18
1745 See Also
1746 ========
1748 rank, unrank_lex
1749 """
1750 perm = self.array_form[:]
1751 n = len(perm)
1752 i = n - 2
1753 while perm[i + 1] < perm[i]:
1754 i -= 1
1755 if i == -1:
1756 return None
1757 else:
1758 j = n - 1
1759 while perm[j] < perm[i]:
1760 j -= 1
1761 perm[j], perm[i] = perm[i], perm[j]
1762 i += 1
1763 j = n - 1
1764 while i < j:
1765 perm[j], perm[i] = perm[i], perm[j]
1766 i += 1
1767 j -= 1
1768 return self._af_new(perm)
1770 @classmethod
1771 def unrank_nonlex(self, n, r):
1772 """
1773 This is a linear time unranking algorithm that does not
1774 respect lexicographic order [3].
1776 Examples
1777 ========
1779 >>> from sympy.combinatorics import Permutation
1780 >>> from sympy import init_printing
1781 >>> init_printing(perm_cyclic=False, pretty_print=False)
1782 >>> Permutation.unrank_nonlex(4, 5)
1783 Permutation([2, 0, 3, 1])
1784 >>> Permutation.unrank_nonlex(4, -1)
1785 Permutation([0, 1, 2, 3])
1787 See Also
1788 ========
1790 next_nonlex, rank_nonlex
1791 """
1792 def _unrank1(n, r, a):
1793 if n > 0:
1794 a[n - 1], a[r % n] = a[r % n], a[n - 1]
1795 _unrank1(n - 1, r//n, a)
1797 id_perm = list(range(n))
1798 n = int(n)
1799 r = r % ifac(n)
1800 _unrank1(n, r, id_perm)
1801 return self._af_new(id_perm)
1803 def rank_nonlex(self, inv_perm=None):
1804 """
1805 This is a linear time ranking algorithm that does not
1806 enforce lexicographic order [3].
1809 Examples
1810 ========
1812 >>> from sympy.combinatorics import Permutation
1813 >>> p = Permutation([0, 1, 2, 3])
1814 >>> p.rank_nonlex()
1815 23
1817 See Also
1818 ========
1820 next_nonlex, unrank_nonlex
1821 """
1822 def _rank1(n, perm, inv_perm):
1823 if n == 1:
1824 return 0
1825 s = perm[n - 1]
1826 t = inv_perm[n - 1]
1827 perm[n - 1], perm[t] = perm[t], s
1828 inv_perm[n - 1], inv_perm[s] = inv_perm[s], t
1829 return s + n*_rank1(n - 1, perm, inv_perm)
1831 if inv_perm is None:
1832 inv_perm = (~self).array_form
1833 if not inv_perm:
1834 return 0
1835 perm = self.array_form[:]
1836 r = _rank1(len(perm), perm, inv_perm)
1837 return r
1839 def next_nonlex(self):
1840 """
1841 Returns the next permutation in nonlex order [3].
1842 If self is the last permutation in this order it returns None.
1844 Examples
1845 ========
1847 >>> from sympy.combinatorics import Permutation
1848 >>> from sympy import init_printing
1849 >>> init_printing(perm_cyclic=False, pretty_print=False)
1850 >>> p = Permutation([2, 0, 3, 1]); p.rank_nonlex()
1851 5
1852 >>> p = p.next_nonlex(); p
1853 Permutation([3, 0, 1, 2])
1854 >>> p.rank_nonlex()
1855 6
1857 See Also
1858 ========
1860 rank_nonlex, unrank_nonlex
1861 """
1862 r = self.rank_nonlex()
1863 if r == ifac(self.size) - 1:
1864 return None
1865 return self.unrank_nonlex(self.size, r + 1)
1867 def rank(self):
1868 """
1869 Returns the lexicographic rank of the permutation.
1871 Examples
1872 ========
1874 >>> from sympy.combinatorics import Permutation
1875 >>> p = Permutation([0, 1, 2, 3])
1876 >>> p.rank()
1877 0
1878 >>> p = Permutation([3, 2, 1, 0])
1879 >>> p.rank()
1880 23
1882 See Also
1883 ========
1885 next_lex, unrank_lex, cardinality, length, order, size
1886 """
1887 if self._rank is not None:
1888 return self._rank
1889 rank = 0
1890 rho = self.array_form[:]
1891 n = self.size - 1
1892 size = n + 1
1893 psize = int(ifac(n))
1894 for j in range(size - 1):
1895 rank += rho[j]*psize
1896 for i in range(j + 1, size):
1897 if rho[i] > rho[j]:
1898 rho[i] -= 1
1899 psize //= n
1900 n -= 1
1901 self._rank = rank
1902 return rank
1904 @property
1905 def cardinality(self):
1906 """
1907 Returns the number of all possible permutations.
1909 Examples
1910 ========
1912 >>> from sympy.combinatorics import Permutation
1913 >>> p = Permutation([0, 1, 2, 3])
1914 >>> p.cardinality
1915 24
1917 See Also
1918 ========
1920 length, order, rank, size
1921 """
1922 return int(ifac(self.size))
1924 def parity(self):
1925 """
1926 Computes the parity of a permutation.
1928 Explanation
1929 ===========
1931 The parity of a permutation reflects the parity of the
1932 number of inversions in the permutation, i.e., the
1933 number of pairs of x and y such that ``x > y`` but ``p[x] < p[y]``.
1935 Examples
1936 ========
1938 >>> from sympy.combinatorics import Permutation
1939 >>> p = Permutation([0, 1, 2, 3])
1940 >>> p.parity()
1941 0
1942 >>> p = Permutation([3, 2, 0, 1])
1943 >>> p.parity()
1944 1
1946 See Also
1947 ========
1949 _af_parity
1950 """
1951 if self._cyclic_form is not None:
1952 return (self.size - self.cycles) % 2
1954 return _af_parity(self.array_form)
1956 @property
1957 def is_even(self):
1958 """
1959 Checks if a permutation is even.
1961 Examples
1962 ========
1964 >>> from sympy.combinatorics import Permutation
1965 >>> p = Permutation([0, 1, 2, 3])
1966 >>> p.is_even
1967 True
1968 >>> p = Permutation([3, 2, 1, 0])
1969 >>> p.is_even
1970 True
1972 See Also
1973 ========
1975 is_odd
1976 """
1977 return not self.is_odd
1979 @property
1980 def is_odd(self):
1981 """
1982 Checks if a permutation is odd.
1984 Examples
1985 ========
1987 >>> from sympy.combinatorics import Permutation
1988 >>> p = Permutation([0, 1, 2, 3])
1989 >>> p.is_odd
1990 False
1991 >>> p = Permutation([3, 2, 0, 1])
1992 >>> p.is_odd
1993 True
1995 See Also
1996 ========
1998 is_even
1999 """
2000 return bool(self.parity() % 2)
2002 @property
2003 def is_Singleton(self):
2004 """
2005 Checks to see if the permutation contains only one number and is
2006 thus the only possible permutation of this set of numbers
2008 Examples
2009 ========
2011 >>> from sympy.combinatorics import Permutation
2012 >>> Permutation([0]).is_Singleton
2013 True
2014 >>> Permutation([0, 1]).is_Singleton
2015 False
2017 See Also
2018 ========
2020 is_Empty
2021 """
2022 return self.size == 1
2024 @property
2025 def is_Empty(self):
2026 """
2027 Checks to see if the permutation is a set with zero elements
2029 Examples
2030 ========
2032 >>> from sympy.combinatorics import Permutation
2033 >>> Permutation([]).is_Empty
2034 True
2035 >>> Permutation([0]).is_Empty
2036 False
2038 See Also
2039 ========
2041 is_Singleton
2042 """
2043 return self.size == 0
2045 @property
2046 def is_identity(self):
2047 return self.is_Identity
2049 @property
2050 def is_Identity(self):
2051 """
2052 Returns True if the Permutation is an identity permutation.
2054 Examples
2055 ========
2057 >>> from sympy.combinatorics import Permutation
2058 >>> p = Permutation([])
2059 >>> p.is_Identity
2060 True
2061 >>> p = Permutation([[0], [1], [2]])
2062 >>> p.is_Identity
2063 True
2064 >>> p = Permutation([0, 1, 2])
2065 >>> p.is_Identity
2066 True
2067 >>> p = Permutation([0, 2, 1])
2068 >>> p.is_Identity
2069 False
2071 See Also
2072 ========
2074 order
2075 """
2076 af = self.array_form
2077 return not af or all(i == af[i] for i in range(self.size))
2079 def ascents(self):
2080 """
2081 Returns the positions of ascents in a permutation, ie, the location
2082 where p[i] < p[i+1]
2084 Examples
2085 ========
2087 >>> from sympy.combinatorics import Permutation
2088 >>> p = Permutation([4, 0, 1, 3, 2])
2089 >>> p.ascents()
2090 [1, 2]
2092 See Also
2093 ========
2095 descents, inversions, min, max
2096 """
2097 a = self.array_form
2098 pos = [i for i in range(len(a) - 1) if a[i] < a[i + 1]]
2099 return pos
2101 def descents(self):
2102 """
2103 Returns the positions of descents in a permutation, ie, the location
2104 where p[i] > p[i+1]
2106 Examples
2107 ========
2109 >>> from sympy.combinatorics import Permutation
2110 >>> p = Permutation([4, 0, 1, 3, 2])
2111 >>> p.descents()
2112 [0, 3]
2114 See Also
2115 ========
2117 ascents, inversions, min, max
2118 """
2119 a = self.array_form
2120 pos = [i for i in range(len(a) - 1) if a[i] > a[i + 1]]
2121 return pos
2123 def max(self):
2124 """
2125 The maximum element moved by the permutation.
2127 Examples
2128 ========
2130 >>> from sympy.combinatorics import Permutation
2131 >>> p = Permutation([1, 0, 2, 3, 4])
2132 >>> p.max()
2133 1
2135 See Also
2136 ========
2138 min, descents, ascents, inversions
2139 """
2140 max = 0
2141 a = self.array_form
2142 for i in range(len(a)):
2143 if a[i] != i and a[i] > max:
2144 max = a[i]
2145 return max
2147 def min(self):
2148 """
2149 The minimum element moved by the permutation.
2151 Examples
2152 ========
2154 >>> from sympy.combinatorics import Permutation
2155 >>> p = Permutation([0, 1, 4, 3, 2])
2156 >>> p.min()
2157 2
2159 See Also
2160 ========
2162 max, descents, ascents, inversions
2163 """
2164 a = self.array_form
2165 min = len(a)
2166 for i in range(len(a)):
2167 if a[i] != i and a[i] < min:
2168 min = a[i]
2169 return min
2171 def inversions(self):
2172 """
2173 Computes the number of inversions of a permutation.
2175 Explanation
2176 ===========
2178 An inversion is where i > j but p[i] < p[j].
2180 For small length of p, it iterates over all i and j
2181 values and calculates the number of inversions.
2182 For large length of p, it uses a variation of merge
2183 sort to calculate the number of inversions.
2185 Examples
2186 ========
2188 >>> from sympy.combinatorics import Permutation
2189 >>> p = Permutation([0, 1, 2, 3, 4, 5])
2190 >>> p.inversions()
2191 0
2192 >>> Permutation([3, 2, 1, 0]).inversions()
2193 6
2195 See Also
2196 ========
2198 descents, ascents, min, max
2200 References
2201 ==========
2203 .. [1] https://www.cp.eng.chula.ac.th/~prabhas//teaching/algo/algo2008/count-inv.htm
2205 """
2206 inversions = 0
2207 a = self.array_form
2208 n = len(a)
2209 if n < 130:
2210 for i in range(n - 1):
2211 b = a[i]
2212 for c in a[i + 1:]:
2213 if b > c:
2214 inversions += 1
2215 else:
2216 k = 1
2217 right = 0
2218 arr = a[:]
2219 temp = a[:]
2220 while k < n:
2221 i = 0
2222 while i + k < n:
2223 right = i + k * 2 - 1
2224 if right >= n:
2225 right = n - 1
2226 inversions += _merge(arr, temp, i, i + k, right)
2227 i = i + k * 2
2228 k = k * 2
2229 return inversions
2231 def commutator(self, x):
2232 """Return the commutator of ``self`` and ``x``: ``~x*~self*x*self``
2234 If f and g are part of a group, G, then the commutator of f and g
2235 is the group identity iff f and g commute, i.e. fg == gf.
2237 Examples
2238 ========
2240 >>> from sympy.combinatorics import Permutation
2241 >>> from sympy import init_printing
2242 >>> init_printing(perm_cyclic=False, pretty_print=False)
2243 >>> p = Permutation([0, 2, 3, 1])
2244 >>> x = Permutation([2, 0, 3, 1])
2245 >>> c = p.commutator(x); c
2246 Permutation([2, 1, 3, 0])
2247 >>> c == ~x*~p*x*p
2248 True
2250 >>> I = Permutation(3)
2251 >>> p = [I + i for i in range(6)]
2252 >>> for i in range(len(p)):
2253 ... for j in range(len(p)):
2254 ... c = p[i].commutator(p[j])
2255 ... if p[i]*p[j] == p[j]*p[i]:
2256 ... assert c == I
2257 ... else:
2258 ... assert c != I
2259 ...
2261 References
2262 ==========
2264 .. [1] https://en.wikipedia.org/wiki/Commutator
2265 """
2267 a = self.array_form
2268 b = x.array_form
2269 n = len(a)
2270 if len(b) != n:
2271 raise ValueError("The permutations must be of equal size.")
2272 inva = [None]*n
2273 for i in range(n):
2274 inva[a[i]] = i
2275 invb = [None]*n
2276 for i in range(n):
2277 invb[b[i]] = i
2278 return self._af_new([a[b[inva[i]]] for i in invb])
2280 def signature(self):
2281 """
2282 Gives the signature of the permutation needed to place the
2283 elements of the permutation in canonical order.
2285 The signature is calculated as (-1)^<number of inversions>
2287 Examples
2288 ========
2290 >>> from sympy.combinatorics import Permutation
2291 >>> p = Permutation([0, 1, 2])
2292 >>> p.inversions()
2293 0
2294 >>> p.signature()
2295 1
2296 >>> q = Permutation([0,2,1])
2297 >>> q.inversions()
2298 1
2299 >>> q.signature()
2300 -1
2302 See Also
2303 ========
2305 inversions
2306 """
2307 if self.is_even:
2308 return 1
2309 return -1
2311 def order(self):
2312 """
2313 Computes the order of a permutation.
2315 When the permutation is raised to the power of its
2316 order it equals the identity permutation.
2318 Examples
2319 ========
2321 >>> from sympy.combinatorics import Permutation
2322 >>> from sympy import init_printing
2323 >>> init_printing(perm_cyclic=False, pretty_print=False)
2324 >>> p = Permutation([3, 1, 5, 2, 4, 0])
2325 >>> p.order()
2326 4
2327 >>> (p**(p.order()))
2328 Permutation([], size=6)
2330 See Also
2331 ========
2333 identity, cardinality, length, rank, size
2334 """
2336 return reduce(lcm, [len(cycle) for cycle in self.cyclic_form], 1)
2338 def length(self):
2339 """
2340 Returns the number of integers moved by a permutation.
2342 Examples
2343 ========
2345 >>> from sympy.combinatorics import Permutation
2346 >>> Permutation([0, 3, 2, 1]).length()
2347 2
2348 >>> Permutation([[0, 1], [2, 3]]).length()
2349 4
2351 See Also
2352 ========
2354 min, max, support, cardinality, order, rank, size
2355 """
2357 return len(self.support())
2359 @property
2360 def cycle_structure(self):
2361 """Return the cycle structure of the permutation as a dictionary
2362 indicating the multiplicity of each cycle length.
2364 Examples
2365 ========
2367 >>> from sympy.combinatorics import Permutation
2368 >>> Permutation(3).cycle_structure
2369 {1: 4}
2370 >>> Permutation(0, 4, 3)(1, 2)(5, 6).cycle_structure
2371 {2: 2, 3: 1}
2372 """
2373 if self._cycle_structure:
2374 rv = self._cycle_structure
2375 else:
2376 rv = defaultdict(int)
2377 singletons = self.size
2378 for c in self.cyclic_form:
2379 rv[len(c)] += 1
2380 singletons -= len(c)
2381 if singletons:
2382 rv[1] = singletons
2383 self._cycle_structure = rv
2384 return dict(rv) # make a copy
2386 @property
2387 def cycles(self):
2388 """
2389 Returns the number of cycles contained in the permutation
2390 (including singletons).
2392 Examples
2393 ========
2395 >>> from sympy.combinatorics import Permutation
2396 >>> Permutation([0, 1, 2]).cycles
2397 3
2398 >>> Permutation([0, 1, 2]).full_cyclic_form
2399 [[0], [1], [2]]
2400 >>> Permutation(0, 1)(2, 3).cycles
2401 2
2403 See Also
2404 ========
2405 sympy.functions.combinatorial.numbers.stirling
2406 """
2407 return len(self.full_cyclic_form)
2409 def index(self):
2410 """
2411 Returns the index of a permutation.
2413 The index of a permutation is the sum of all subscripts j such
2414 that p[j] is greater than p[j+1].
2416 Examples
2417 ========
2419 >>> from sympy.combinatorics import Permutation
2420 >>> p = Permutation([3, 0, 2, 1, 4])
2421 >>> p.index()
2422 2
2423 """
2424 a = self.array_form
2426 return sum([j for j in range(len(a) - 1) if a[j] > a[j + 1]])
2428 def runs(self):
2429 """
2430 Returns the runs of a permutation.
2432 An ascending sequence in a permutation is called a run [5].
2435 Examples
2436 ========
2438 >>> from sympy.combinatorics import Permutation
2439 >>> p = Permutation([2, 5, 7, 3, 6, 0, 1, 4, 8])
2440 >>> p.runs()
2441 [[2, 5, 7], [3, 6], [0, 1, 4, 8]]
2442 >>> q = Permutation([1,3,2,0])
2443 >>> q.runs()
2444 [[1, 3], [2], [0]]
2445 """
2446 return runs(self.array_form)
2448 def inversion_vector(self):
2449 """Return the inversion vector of the permutation.
2451 The inversion vector consists of elements whose value
2452 indicates the number of elements in the permutation
2453 that are lesser than it and lie on its right hand side.
2455 The inversion vector is the same as the Lehmer encoding of a
2456 permutation.
2458 Examples
2459 ========
2461 >>> from sympy.combinatorics import Permutation
2462 >>> p = Permutation([4, 8, 0, 7, 1, 5, 3, 6, 2])
2463 >>> p.inversion_vector()
2464 [4, 7, 0, 5, 0, 2, 1, 1]
2465 >>> p = Permutation([3, 2, 1, 0])
2466 >>> p.inversion_vector()
2467 [3, 2, 1]
2469 The inversion vector increases lexicographically with the rank
2470 of the permutation, the -ith element cycling through 0..i.
2472 >>> p = Permutation(2)
2473 >>> while p:
2474 ... print('%s %s %s' % (p, p.inversion_vector(), p.rank()))
2475 ... p = p.next_lex()
2476 (2) [0, 0] 0
2477 (1 2) [0, 1] 1
2478 (2)(0 1) [1, 0] 2
2479 (0 1 2) [1, 1] 3
2480 (0 2 1) [2, 0] 4
2481 (0 2) [2, 1] 5
2483 See Also
2484 ========
2486 from_inversion_vector
2487 """
2488 self_array_form = self.array_form
2489 n = len(self_array_form)
2490 inversion_vector = [0] * (n - 1)
2492 for i in range(n - 1):
2493 val = 0
2494 for j in range(i + 1, n):
2495 if self_array_form[j] < self_array_form[i]:
2496 val += 1
2497 inversion_vector[i] = val
2498 return inversion_vector
2500 def rank_trotterjohnson(self):
2501 """
2502 Returns the Trotter Johnson rank, which we get from the minimal
2503 change algorithm. See [4] section 2.4.
2505 Examples
2506 ========
2508 >>> from sympy.combinatorics import Permutation
2509 >>> p = Permutation([0, 1, 2, 3])
2510 >>> p.rank_trotterjohnson()
2511 0
2512 >>> p = Permutation([0, 2, 1, 3])
2513 >>> p.rank_trotterjohnson()
2514 7
2516 See Also
2517 ========
2519 unrank_trotterjohnson, next_trotterjohnson
2520 """
2521 if self.array_form == [] or self.is_Identity:
2522 return 0
2523 if self.array_form == [1, 0]:
2524 return 1
2525 perm = self.array_form
2526 n = self.size
2527 rank = 0
2528 for j in range(1, n):
2529 k = 1
2530 i = 0
2531 while perm[i] != j:
2532 if perm[i] < j:
2533 k += 1
2534 i += 1
2535 j1 = j + 1
2536 if rank % 2 == 0:
2537 rank = j1*rank + j1 - k
2538 else:
2539 rank = j1*rank + k - 1
2540 return rank
2542 @classmethod
2543 def unrank_trotterjohnson(cls, size, rank):
2544 """
2545 Trotter Johnson permutation unranking. See [4] section 2.4.
2547 Examples
2548 ========
2550 >>> from sympy.combinatorics import Permutation
2551 >>> from sympy import init_printing
2552 >>> init_printing(perm_cyclic=False, pretty_print=False)
2553 >>> Permutation.unrank_trotterjohnson(5, 10)
2554 Permutation([0, 3, 1, 2, 4])
2556 See Also
2557 ========
2559 rank_trotterjohnson, next_trotterjohnson
2560 """
2561 perm = [0]*size
2562 r2 = 0
2563 n = ifac(size)
2564 pj = 1
2565 for j in range(2, size + 1):
2566 pj *= j
2567 r1 = (rank * pj) // n
2568 k = r1 - j*r2
2569 if r2 % 2 == 0:
2570 for i in range(j - 1, j - k - 1, -1):
2571 perm[i] = perm[i - 1]
2572 perm[j - k - 1] = j - 1
2573 else:
2574 for i in range(j - 1, k, -1):
2575 perm[i] = perm[i - 1]
2576 perm[k] = j - 1
2577 r2 = r1
2578 return cls._af_new(perm)
2580 def next_trotterjohnson(self):
2581 """
2582 Returns the next permutation in Trotter-Johnson order.
2583 If self is the last permutation it returns None.
2584 See [4] section 2.4. If it is desired to generate all such
2585 permutations, they can be generated in order more quickly
2586 with the ``generate_bell`` function.
2588 Examples
2589 ========
2591 >>> from sympy.combinatorics import Permutation
2592 >>> from sympy import init_printing
2593 >>> init_printing(perm_cyclic=False, pretty_print=False)
2594 >>> p = Permutation([3, 0, 2, 1])
2595 >>> p.rank_trotterjohnson()
2596 4
2597 >>> p = p.next_trotterjohnson(); p
2598 Permutation([0, 3, 2, 1])
2599 >>> p.rank_trotterjohnson()
2600 5
2602 See Also
2603 ========
2605 rank_trotterjohnson, unrank_trotterjohnson, sympy.utilities.iterables.generate_bell
2606 """
2607 pi = self.array_form[:]
2608 n = len(pi)
2609 st = 0
2610 rho = pi[:]
2611 done = False
2612 m = n-1
2613 while m > 0 and not done:
2614 d = rho.index(m)
2615 for i in range(d, m):
2616 rho[i] = rho[i + 1]
2617 par = _af_parity(rho[:m])
2618 if par == 1:
2619 if d == m:
2620 m -= 1
2621 else:
2622 pi[st + d], pi[st + d + 1] = pi[st + d + 1], pi[st + d]
2623 done = True
2624 else:
2625 if d == 0:
2626 m -= 1
2627 st += 1
2628 else:
2629 pi[st + d], pi[st + d - 1] = pi[st + d - 1], pi[st + d]
2630 done = True
2631 if m == 0:
2632 return None
2633 return self._af_new(pi)
2635 def get_precedence_matrix(self):
2636 """
2637 Gets the precedence matrix. This is used for computing the
2638 distance between two permutations.
2640 Examples
2641 ========
2643 >>> from sympy.combinatorics import Permutation
2644 >>> from sympy import init_printing
2645 >>> init_printing(perm_cyclic=False, pretty_print=False)
2646 >>> p = Permutation.josephus(3, 6, 1)
2647 >>> p
2648 Permutation([2, 5, 3, 1, 4, 0])
2649 >>> p.get_precedence_matrix()
2650 Matrix([
2651 [0, 0, 0, 0, 0, 0],
2652 [1, 0, 0, 0, 1, 0],
2653 [1, 1, 0, 1, 1, 1],
2654 [1, 1, 0, 0, 1, 0],
2655 [1, 0, 0, 0, 0, 0],
2656 [1, 1, 0, 1, 1, 0]])
2658 See Also
2659 ========
2661 get_precedence_distance, get_adjacency_matrix, get_adjacency_distance
2662 """
2663 m = zeros(self.size)
2664 perm = self.array_form
2665 for i in range(m.rows):
2666 for j in range(i + 1, m.cols):
2667 m[perm[i], perm[j]] = 1
2668 return m
2670 def get_precedence_distance(self, other):
2671 """
2672 Computes the precedence distance between two permutations.
2674 Explanation
2675 ===========
2677 Suppose p and p' represent n jobs. The precedence metric
2678 counts the number of times a job j is preceded by job i
2679 in both p and p'. This metric is commutative.
2681 Examples
2682 ========
2684 >>> from sympy.combinatorics import Permutation
2685 >>> p = Permutation([2, 0, 4, 3, 1])
2686 >>> q = Permutation([3, 1, 2, 4, 0])
2687 >>> p.get_precedence_distance(q)
2688 7
2689 >>> q.get_precedence_distance(p)
2690 7
2692 See Also
2693 ========
2695 get_precedence_matrix, get_adjacency_matrix, get_adjacency_distance
2696 """
2697 if self.size != other.size:
2698 raise ValueError("The permutations must be of equal size.")
2699 self_prec_mat = self.get_precedence_matrix()
2700 other_prec_mat = other.get_precedence_matrix()
2701 n_prec = 0
2702 for i in range(self.size):
2703 for j in range(self.size):
2704 if i == j:
2705 continue
2706 if self_prec_mat[i, j] * other_prec_mat[i, j] == 1:
2707 n_prec += 1
2708 d = self.size * (self.size - 1)//2 - n_prec
2709 return d
2711 def get_adjacency_matrix(self):
2712 """
2713 Computes the adjacency matrix of a permutation.
2715 Explanation
2716 ===========
2718 If job i is adjacent to job j in a permutation p
2719 then we set m[i, j] = 1 where m is the adjacency
2720 matrix of p.
2722 Examples
2723 ========
2725 >>> from sympy.combinatorics import Permutation
2726 >>> p = Permutation.josephus(3, 6, 1)
2727 >>> p.get_adjacency_matrix()
2728 Matrix([
2729 [0, 0, 0, 0, 0, 0],
2730 [0, 0, 0, 0, 1, 0],
2731 [0, 0, 0, 0, 0, 1],
2732 [0, 1, 0, 0, 0, 0],
2733 [1, 0, 0, 0, 0, 0],
2734 [0, 0, 0, 1, 0, 0]])
2735 >>> q = Permutation([0, 1, 2, 3])
2736 >>> q.get_adjacency_matrix()
2737 Matrix([
2738 [0, 1, 0, 0],
2739 [0, 0, 1, 0],
2740 [0, 0, 0, 1],
2741 [0, 0, 0, 0]])
2743 See Also
2744 ========
2746 get_precedence_matrix, get_precedence_distance, get_adjacency_distance
2747 """
2748 m = zeros(self.size)
2749 perm = self.array_form
2750 for i in range(self.size - 1):
2751 m[perm[i], perm[i + 1]] = 1
2752 return m
2754 def get_adjacency_distance(self, other):
2755 """
2756 Computes the adjacency distance between two permutations.
2758 Explanation
2759 ===========
2761 This metric counts the number of times a pair i,j of jobs is
2762 adjacent in both p and p'. If n_adj is this quantity then
2763 the adjacency distance is n - n_adj - 1 [1]
2765 [1] Reeves, Colin R. Landscapes, Operators and Heuristic search, Annals
2766 of Operational Research, 86, pp 473-490. (1999)
2769 Examples
2770 ========
2772 >>> from sympy.combinatorics import Permutation
2773 >>> p = Permutation([0, 3, 1, 2, 4])
2774 >>> q = Permutation.josephus(4, 5, 2)
2775 >>> p.get_adjacency_distance(q)
2776 3
2777 >>> r = Permutation([0, 2, 1, 4, 3])
2778 >>> p.get_adjacency_distance(r)
2779 4
2781 See Also
2782 ========
2784 get_precedence_matrix, get_precedence_distance, get_adjacency_matrix
2785 """
2786 if self.size != other.size:
2787 raise ValueError("The permutations must be of the same size.")
2788 self_adj_mat = self.get_adjacency_matrix()
2789 other_adj_mat = other.get_adjacency_matrix()
2790 n_adj = 0
2791 for i in range(self.size):
2792 for j in range(self.size):
2793 if i == j:
2794 continue
2795 if self_adj_mat[i, j] * other_adj_mat[i, j] == 1:
2796 n_adj += 1
2797 d = self.size - n_adj - 1
2798 return d
2800 def get_positional_distance(self, other):
2801 """
2802 Computes the positional distance between two permutations.
2804 Examples
2805 ========
2807 >>> from sympy.combinatorics import Permutation
2808 >>> p = Permutation([0, 3, 1, 2, 4])
2809 >>> q = Permutation.josephus(4, 5, 2)
2810 >>> r = Permutation([3, 1, 4, 0, 2])
2811 >>> p.get_positional_distance(q)
2812 12
2813 >>> p.get_positional_distance(r)
2814 12
2816 See Also
2817 ========
2819 get_precedence_distance, get_adjacency_distance
2820 """
2821 a = self.array_form
2822 b = other.array_form
2823 if len(a) != len(b):
2824 raise ValueError("The permutations must be of the same size.")
2825 return sum([abs(a[i] - b[i]) for i in range(len(a))])
2827 @classmethod
2828 def josephus(cls, m, n, s=1):
2829 """Return as a permutation the shuffling of range(n) using the Josephus
2830 scheme in which every m-th item is selected until all have been chosen.
2831 The returned permutation has elements listed by the order in which they
2832 were selected.
2834 The parameter ``s`` stops the selection process when there are ``s``
2835 items remaining and these are selected by continuing the selection,
2836 counting by 1 rather than by ``m``.
2838 Consider selecting every 3rd item from 6 until only 2 remain::
2840 choices chosen
2841 ======== ======
2842 012345
2843 01 345 2
2844 01 34 25
2845 01 4 253
2846 0 4 2531
2847 0 25314
2848 253140
2850 Examples
2851 ========
2853 >>> from sympy.combinatorics import Permutation
2854 >>> Permutation.josephus(3, 6, 2).array_form
2855 [2, 5, 3, 1, 4, 0]
2857 References
2858 ==========
2860 .. [1] https://en.wikipedia.org/wiki/Flavius_Josephus
2861 .. [2] https://en.wikipedia.org/wiki/Josephus_problem
2862 .. [3] https://web.archive.org/web/20171008094331/http://www.wou.edu/~burtonl/josephus.html
2864 """
2865 from collections import deque
2866 m -= 1
2867 Q = deque(list(range(n)))
2868 perm = []
2869 while len(Q) > max(s, 1):
2870 for dp in range(m):
2871 Q.append(Q.popleft())
2872 perm.append(Q.popleft())
2873 perm.extend(list(Q))
2874 return cls(perm)
2876 @classmethod
2877 def from_inversion_vector(cls, inversion):
2878 """
2879 Calculates the permutation from the inversion vector.
2881 Examples
2882 ========
2884 >>> from sympy.combinatorics import Permutation
2885 >>> from sympy import init_printing
2886 >>> init_printing(perm_cyclic=False, pretty_print=False)
2887 >>> Permutation.from_inversion_vector([3, 2, 1, 0, 0])
2888 Permutation([3, 2, 1, 0, 4, 5])
2890 """
2891 size = len(inversion)
2892 N = list(range(size + 1))
2893 perm = []
2894 try:
2895 for k in range(size):
2896 val = N[inversion[k]]
2897 perm.append(val)
2898 N.remove(val)
2899 except IndexError:
2900 raise ValueError("The inversion vector is not valid.")
2901 perm.extend(N)
2902 return cls._af_new(perm)
2904 @classmethod
2905 def random(cls, n):
2906 """
2907 Generates a random permutation of length ``n``.
2909 Uses the underlying Python pseudo-random number generator.
2911 Examples
2912 ========
2914 >>> from sympy.combinatorics import Permutation
2915 >>> Permutation.random(2) in (Permutation([1, 0]), Permutation([0, 1]))
2916 True
2918 """
2919 perm_array = list(range(n))
2920 random.shuffle(perm_array)
2921 return cls._af_new(perm_array)
2923 @classmethod
2924 def unrank_lex(cls, size, rank):
2925 """
2926 Lexicographic permutation unranking.
2928 Examples
2929 ========
2931 >>> from sympy.combinatorics import Permutation
2932 >>> from sympy import init_printing
2933 >>> init_printing(perm_cyclic=False, pretty_print=False)
2934 >>> a = Permutation.unrank_lex(5, 10)
2935 >>> a.rank()
2936 10
2937 >>> a
2938 Permutation([0, 2, 4, 1, 3])
2940 See Also
2941 ========
2943 rank, next_lex
2944 """
2945 perm_array = [0] * size
2946 psize = 1
2947 for i in range(size):
2948 new_psize = psize*(i + 1)
2949 d = (rank % new_psize) // psize
2950 rank -= d*psize
2951 perm_array[size - i - 1] = d
2952 for j in range(size - i, size):
2953 if perm_array[j] > d - 1:
2954 perm_array[j] += 1
2955 psize = new_psize
2956 return cls._af_new(perm_array)
2958 def resize(self, n):
2959 """Resize the permutation to the new size ``n``.
2961 Parameters
2962 ==========
2964 n : int
2965 The new size of the permutation.
2967 Raises
2968 ======
2970 ValueError
2971 If the permutation cannot be resized to the given size.
2972 This may only happen when resized to a smaller size than
2973 the original.
2975 Examples
2976 ========
2978 >>> from sympy.combinatorics import Permutation
2980 Increasing the size of a permutation:
2982 >>> p = Permutation(0, 1, 2)
2983 >>> p = p.resize(5)
2984 >>> p
2985 (4)(0 1 2)
2987 Decreasing the size of the permutation:
2989 >>> p = p.resize(4)
2990 >>> p
2991 (3)(0 1 2)
2993 If resizing to the specific size breaks the cycles:
2995 >>> p.resize(2)
2996 Traceback (most recent call last):
2997 ...
2998 ValueError: The permutation cannot be resized to 2 because the
2999 cycle (0, 1, 2) may break.
3000 """
3001 aform = self.array_form
3002 l = len(aform)
3003 if n > l:
3004 aform += list(range(l, n))
3005 return Permutation._af_new(aform)
3007 elif n < l:
3008 cyclic_form = self.full_cyclic_form
3009 new_cyclic_form = []
3010 for cycle in cyclic_form:
3011 cycle_min = min(cycle)
3012 cycle_max = max(cycle)
3013 if cycle_min <= n-1:
3014 if cycle_max > n-1:
3015 raise ValueError(
3016 "The permutation cannot be resized to {} "
3017 "because the cycle {} may break."
3018 .format(n, tuple(cycle)))
3020 new_cyclic_form.append(cycle)
3021 return Permutation(new_cyclic_form)
3023 return self
3025 # XXX Deprecated flag
3026 print_cyclic = None
3029def _merge(arr, temp, left, mid, right):
3030 """
3031 Merges two sorted arrays and calculates the inversion count.
3033 Helper function for calculating inversions. This method is
3034 for internal use only.
3035 """
3036 i = k = left
3037 j = mid
3038 inv_count = 0
3039 while i < mid and j <= right:
3040 if arr[i] < arr[j]:
3041 temp[k] = arr[i]
3042 k += 1
3043 i += 1
3044 else:
3045 temp[k] = arr[j]
3046 k += 1
3047 j += 1
3048 inv_count += (mid -i)
3049 while i < mid:
3050 temp[k] = arr[i]
3051 k += 1
3052 i += 1
3053 if j <= right:
3054 k += right - j + 1
3055 j += right - j + 1
3056 arr[left:k + 1] = temp[left:k + 1]
3057 else:
3058 arr[left:right + 1] = temp[left:right + 1]
3059 return inv_count
3061Perm = Permutation
3062_af_new = Perm._af_new
3065class AppliedPermutation(Expr):
3066 """A permutation applied to a symbolic variable.
3068 Parameters
3069 ==========
3071 perm : Permutation
3072 x : Expr
3074 Examples
3075 ========
3077 >>> from sympy import Symbol
3078 >>> from sympy.combinatorics import Permutation
3080 Creating a symbolic permutation function application:
3082 >>> x = Symbol('x')
3083 >>> p = Permutation(0, 1, 2)
3084 >>> p.apply(x)
3085 AppliedPermutation((0 1 2), x)
3086 >>> _.subs(x, 1)
3087 2
3088 """
3089 def __new__(cls, perm, x, evaluate=None):
3090 if evaluate is None:
3091 evaluate = global_parameters.evaluate
3093 perm = _sympify(perm)
3094 x = _sympify(x)
3096 if not isinstance(perm, Permutation):
3097 raise ValueError("{} must be a Permutation instance."
3098 .format(perm))
3100 if evaluate:
3101 if x.is_Integer:
3102 return perm.apply(x)
3104 obj = super().__new__(cls, perm, x)
3105 return obj
3108@dispatch(Permutation, Permutation)
3109def _eval_is_eq(lhs, rhs):
3110 if lhs._size != rhs._size:
3111 return None
3112 return lhs._array_form == rhs._array_form