Coverage for /usr/lib/python3/dist-packages/sympy/combinatorics/free_groups.py: 21%
501 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1from __future__ import annotations
3from sympy.core import S
4from sympy.core.expr import Expr
5from sympy.core.symbol import Symbol, symbols as _symbols
6from sympy.core.sympify import CantSympify
7from sympy.printing.defaults import DefaultPrinting
8from sympy.utilities import public
9from sympy.utilities.iterables import flatten, is_sequence
10from sympy.utilities.magic import pollute
11from sympy.utilities.misc import as_int
14@public
15def free_group(symbols):
16 """Construct a free group returning ``(FreeGroup, (f_0, f_1, ..., f_(n-1))``.
18 Parameters
19 ==========
21 symbols : str, Symbol/Expr or sequence of str, Symbol/Expr (may be empty)
23 Examples
24 ========
26 >>> from sympy.combinatorics import free_group
27 >>> F, x, y, z = free_group("x, y, z")
28 >>> F
29 <free group on the generators (x, y, z)>
30 >>> x**2*y**-1
31 x**2*y**-1
32 >>> type(_)
33 <class 'sympy.combinatorics.free_groups.FreeGroupElement'>
35 """
36 _free_group = FreeGroup(symbols)
37 return (_free_group,) + tuple(_free_group.generators)
39@public
40def xfree_group(symbols):
41 """Construct a free group returning ``(FreeGroup, (f_0, f_1, ..., f_(n-1)))``.
43 Parameters
44 ==========
46 symbols : str, Symbol/Expr or sequence of str, Symbol/Expr (may be empty)
48 Examples
49 ========
51 >>> from sympy.combinatorics.free_groups import xfree_group
52 >>> F, (x, y, z) = xfree_group("x, y, z")
53 >>> F
54 <free group on the generators (x, y, z)>
55 >>> y**2*x**-2*z**-1
56 y**2*x**-2*z**-1
57 >>> type(_)
58 <class 'sympy.combinatorics.free_groups.FreeGroupElement'>
60 """
61 _free_group = FreeGroup(symbols)
62 return (_free_group, _free_group.generators)
64@public
65def vfree_group(symbols):
66 """Construct a free group and inject ``f_0, f_1, ..., f_(n-1)`` as symbols
67 into the global namespace.
69 Parameters
70 ==========
72 symbols : str, Symbol/Expr or sequence of str, Symbol/Expr (may be empty)
74 Examples
75 ========
77 >>> from sympy.combinatorics.free_groups import vfree_group
78 >>> vfree_group("x, y, z")
79 <free group on the generators (x, y, z)>
80 >>> x**2*y**-2*z # noqa: F821
81 x**2*y**-2*z
82 >>> type(_)
83 <class 'sympy.combinatorics.free_groups.FreeGroupElement'>
85 """
86 _free_group = FreeGroup(symbols)
87 pollute([sym.name for sym in _free_group.symbols], _free_group.generators)
88 return _free_group
91def _parse_symbols(symbols):
92 if not symbols:
93 return ()
94 if isinstance(symbols, str):
95 return _symbols(symbols, seq=True)
96 elif isinstance(symbols, (Expr, FreeGroupElement)):
97 return (symbols,)
98 elif is_sequence(symbols):
99 if all(isinstance(s, str) for s in symbols):
100 return _symbols(symbols)
101 elif all(isinstance(s, Expr) for s in symbols):
102 return symbols
103 raise ValueError("The type of `symbols` must be one of the following: "
104 "a str, Symbol/Expr or a sequence of "
105 "one of these types")
108##############################################################################
109# FREE GROUP #
110##############################################################################
112_free_group_cache: dict[int, FreeGroup] = {}
114class FreeGroup(DefaultPrinting):
115 """
116 Free group with finite or infinite number of generators. Its input API
117 is that of a str, Symbol/Expr or a sequence of one of
118 these types (which may be empty)
120 See Also
121 ========
123 sympy.polys.rings.PolyRing
125 References
126 ==========
128 .. [1] https://www.gap-system.org/Manuals/doc/ref/chap37.html
130 .. [2] https://en.wikipedia.org/wiki/Free_group
132 """
133 is_associative = True
134 is_group = True
135 is_FreeGroup = True
136 is_PermutationGroup = False
137 relators: list[Expr] = []
139 def __new__(cls, symbols):
140 symbols = tuple(_parse_symbols(symbols))
141 rank = len(symbols)
142 _hash = hash((cls.__name__, symbols, rank))
143 obj = _free_group_cache.get(_hash)
145 if obj is None:
146 obj = object.__new__(cls)
147 obj._hash = _hash
148 obj._rank = rank
149 # dtype method is used to create new instances of FreeGroupElement
150 obj.dtype = type("FreeGroupElement", (FreeGroupElement,), {"group": obj})
151 obj.symbols = symbols
152 obj.generators = obj._generators()
153 obj._gens_set = set(obj.generators)
154 for symbol, generator in zip(obj.symbols, obj.generators):
155 if isinstance(symbol, Symbol):
156 name = symbol.name
157 if hasattr(obj, name):
158 setattr(obj, name, generator)
160 _free_group_cache[_hash] = obj
162 return obj
164 def _generators(group):
165 """Returns the generators of the FreeGroup.
167 Examples
168 ========
170 >>> from sympy.combinatorics import free_group
171 >>> F, x, y, z = free_group("x, y, z")
172 >>> F.generators
173 (x, y, z)
175 """
176 gens = []
177 for sym in group.symbols:
178 elm = ((sym, 1),)
179 gens.append(group.dtype(elm))
180 return tuple(gens)
182 def clone(self, symbols=None):
183 return self.__class__(symbols or self.symbols)
185 def __contains__(self, i):
186 """Return True if ``i`` is contained in FreeGroup."""
187 if not isinstance(i, FreeGroupElement):
188 return False
189 group = i.group
190 return self == group
192 def __hash__(self):
193 return self._hash
195 def __len__(self):
196 return self.rank
198 def __str__(self):
199 if self.rank > 30:
200 str_form = "<free group with %s generators>" % self.rank
201 else:
202 str_form = "<free group on the generators "
203 gens = self.generators
204 str_form += str(gens) + ">"
205 return str_form
207 __repr__ = __str__
209 def __getitem__(self, index):
210 symbols = self.symbols[index]
211 return self.clone(symbols=symbols)
213 def __eq__(self, other):
214 """No ``FreeGroup`` is equal to any "other" ``FreeGroup``.
215 """
216 return self is other
218 def index(self, gen):
219 """Return the index of the generator `gen` from ``(f_0, ..., f_(n-1))``.
221 Examples
222 ========
224 >>> from sympy.combinatorics import free_group
225 >>> F, x, y = free_group("x, y")
226 >>> F.index(y)
227 1
228 >>> F.index(x)
229 0
231 """
232 if isinstance(gen, self.dtype):
233 return self.generators.index(gen)
234 else:
235 raise ValueError("expected a generator of Free Group %s, got %s" % (self, gen))
237 def order(self):
238 """Return the order of the free group.
240 Examples
241 ========
243 >>> from sympy.combinatorics import free_group
244 >>> F, x, y = free_group("x, y")
245 >>> F.order()
246 oo
248 >>> free_group("")[0].order()
249 1
251 """
252 if self.rank == 0:
253 return S.One
254 else:
255 return S.Infinity
257 @property
258 def elements(self):
259 """
260 Return the elements of the free group.
262 Examples
263 ========
265 >>> from sympy.combinatorics import free_group
266 >>> (z,) = free_group("")
267 >>> z.elements
268 {<identity>}
270 """
271 if self.rank == 0:
272 # A set containing Identity element of `FreeGroup` self is returned
273 return {self.identity}
274 else:
275 raise ValueError("Group contains infinitely many elements"
276 ", hence cannot be represented")
278 @property
279 def rank(self):
280 r"""
281 In group theory, the `rank` of a group `G`, denoted `G.rank`,
282 can refer to the smallest cardinality of a generating set
283 for G, that is
285 \operatorname{rank}(G)=\min\{ |X|: X\subseteq G, \left\langle X\right\rangle =G\}.
287 """
288 return self._rank
290 @property
291 def is_abelian(self):
292 """Returns if the group is Abelian.
294 Examples
295 ========
297 >>> from sympy.combinatorics import free_group
298 >>> f, x, y, z = free_group("x y z")
299 >>> f.is_abelian
300 False
302 """
303 return self.rank in (0, 1)
305 @property
306 def identity(self):
307 """Returns the identity element of free group."""
308 return self.dtype()
310 def contains(self, g):
311 """Tests if Free Group element ``g`` belong to self, ``G``.
313 In mathematical terms any linear combination of generators
314 of a Free Group is contained in it.
316 Examples
317 ========
319 >>> from sympy.combinatorics import free_group
320 >>> f, x, y, z = free_group("x y z")
321 >>> f.contains(x**3*y**2)
322 True
324 """
325 if not isinstance(g, FreeGroupElement):
326 return False
327 elif self != g.group:
328 return False
329 else:
330 return True
332 def center(self):
333 """Returns the center of the free group `self`."""
334 return {self.identity}
337############################################################################
338# FreeGroupElement #
339############################################################################
342class FreeGroupElement(CantSympify, DefaultPrinting, tuple):
343 """Used to create elements of FreeGroup. It cannot be used directly to
344 create a free group element. It is called by the `dtype` method of the
345 `FreeGroup` class.
347 """
348 is_assoc_word = True
350 def new(self, init):
351 return self.__class__(init)
353 _hash = None
355 def __hash__(self):
356 _hash = self._hash
357 if _hash is None:
358 self._hash = _hash = hash((self.group, frozenset(tuple(self))))
359 return _hash
361 def copy(self):
362 return self.new(self)
364 @property
365 def is_identity(self):
366 if self.array_form == ():
367 return True
368 else:
369 return False
371 @property
372 def array_form(self):
373 """
374 SymPy provides two different internal kinds of representation
375 of associative words. The first one is called the `array_form`
376 which is a tuple containing `tuples` as its elements, where the
377 size of each tuple is two. At the first position the tuple
378 contains the `symbol-generator`, while at the second position
379 of tuple contains the exponent of that generator at the position.
380 Since elements (i.e. words) do not commute, the indexing of tuple
381 makes that property to stay.
383 The structure in ``array_form`` of ``FreeGroupElement`` is of form:
385 ``( ( symbol_of_gen, exponent ), ( , ), ... ( , ) )``
387 Examples
388 ========
390 >>> from sympy.combinatorics import free_group
391 >>> f, x, y, z = free_group("x y z")
392 >>> (x*z).array_form
393 ((x, 1), (z, 1))
394 >>> (x**2*z*y*x**2).array_form
395 ((x, 2), (z, 1), (y, 1), (x, 2))
397 See Also
398 ========
400 letter_repr
402 """
403 return tuple(self)
405 @property
406 def letter_form(self):
407 """
408 The letter representation of a ``FreeGroupElement`` is a tuple
409 of generator symbols, with each entry corresponding to a group
410 generator. Inverses of the generators are represented by
411 negative generator symbols.
413 Examples
414 ========
416 >>> from sympy.combinatorics import free_group
417 >>> f, a, b, c, d = free_group("a b c d")
418 >>> (a**3).letter_form
419 (a, a, a)
420 >>> (a**2*d**-2*a*b**-4).letter_form
421 (a, a, -d, -d, a, -b, -b, -b, -b)
422 >>> (a**-2*b**3*d).letter_form
423 (-a, -a, b, b, b, d)
425 See Also
426 ========
428 array_form
430 """
431 return tuple(flatten([(i,)*j if j > 0 else (-i,)*(-j)
432 for i, j in self.array_form]))
434 def __getitem__(self, i):
435 group = self.group
436 r = self.letter_form[i]
437 if r.is_Symbol:
438 return group.dtype(((r, 1),))
439 else:
440 return group.dtype(((-r, -1),))
442 def index(self, gen):
443 if len(gen) != 1:
444 raise ValueError()
445 return (self.letter_form).index(gen.letter_form[0])
447 @property
448 def letter_form_elm(self):
449 """
450 """
451 group = self.group
452 r = self.letter_form
453 return [group.dtype(((elm,1),)) if elm.is_Symbol \
454 else group.dtype(((-elm,-1),)) for elm in r]
456 @property
457 def ext_rep(self):
458 """This is called the External Representation of ``FreeGroupElement``
459 """
460 return tuple(flatten(self.array_form))
462 def __contains__(self, gen):
463 return gen.array_form[0][0] in tuple([r[0] for r in self.array_form])
465 def __str__(self):
466 if self.is_identity:
467 return "<identity>"
469 str_form = ""
470 array_form = self.array_form
471 for i in range(len(array_form)):
472 if i == len(array_form) - 1:
473 if array_form[i][1] == 1:
474 str_form += str(array_form[i][0])
475 else:
476 str_form += str(array_form[i][0]) + \
477 "**" + str(array_form[i][1])
478 else:
479 if array_form[i][1] == 1:
480 str_form += str(array_form[i][0]) + "*"
481 else:
482 str_form += str(array_form[i][0]) + \
483 "**" + str(array_form[i][1]) + "*"
484 return str_form
486 __repr__ = __str__
488 def __pow__(self, n):
489 n = as_int(n)
490 group = self.group
491 if n == 0:
492 return group.identity
494 if n < 0:
495 n = -n
496 return (self.inverse())**n
498 result = self
499 for i in range(n - 1):
500 result = result*self
501 # this method can be improved instead of just returning the
502 # multiplication of elements
503 return result
505 def __mul__(self, other):
506 """Returns the product of elements belonging to the same ``FreeGroup``.
508 Examples
509 ========
511 >>> from sympy.combinatorics import free_group
512 >>> f, x, y, z = free_group("x y z")
513 >>> x*y**2*y**-4
514 x*y**-2
515 >>> z*y**-2
516 z*y**-2
517 >>> x**2*y*y**-1*x**-2
518 <identity>
520 """
521 group = self.group
522 if not isinstance(other, group.dtype):
523 raise TypeError("only FreeGroup elements of same FreeGroup can "
524 "be multiplied")
525 if self.is_identity:
526 return other
527 if other.is_identity:
528 return self
529 r = list(self.array_form + other.array_form)
530 zero_mul_simp(r, len(self.array_form) - 1)
531 return group.dtype(tuple(r))
533 def __truediv__(self, other):
534 group = self.group
535 if not isinstance(other, group.dtype):
536 raise TypeError("only FreeGroup elements of same FreeGroup can "
537 "be multiplied")
538 return self*(other.inverse())
540 def __rtruediv__(self, other):
541 group = self.group
542 if not isinstance(other, group.dtype):
543 raise TypeError("only FreeGroup elements of same FreeGroup can "
544 "be multiplied")
545 return other*(self.inverse())
547 def __add__(self, other):
548 return NotImplemented
550 def inverse(self):
551 """
552 Returns the inverse of a ``FreeGroupElement`` element
554 Examples
555 ========
557 >>> from sympy.combinatorics import free_group
558 >>> f, x, y, z = free_group("x y z")
559 >>> x.inverse()
560 x**-1
561 >>> (x*y).inverse()
562 y**-1*x**-1
564 """
565 group = self.group
566 r = tuple([(i, -j) for i, j in self.array_form[::-1]])
567 return group.dtype(r)
569 def order(self):
570 """Find the order of a ``FreeGroupElement``.
572 Examples
573 ========
575 >>> from sympy.combinatorics import free_group
576 >>> f, x, y = free_group("x y")
577 >>> (x**2*y*y**-1*x**-2).order()
578 1
580 """
581 if self.is_identity:
582 return S.One
583 else:
584 return S.Infinity
586 def commutator(self, other):
587 """
588 Return the commutator of `self` and `x`: ``~x*~self*x*self``
590 """
591 group = self.group
592 if not isinstance(other, group.dtype):
593 raise ValueError("commutator of only FreeGroupElement of the same "
594 "FreeGroup exists")
595 else:
596 return self.inverse()*other.inverse()*self*other
598 def eliminate_words(self, words, _all=False, inverse=True):
599 '''
600 Replace each subword from the dictionary `words` by words[subword].
601 If words is a list, replace the words by the identity.
603 '''
604 again = True
605 new = self
606 if isinstance(words, dict):
607 while again:
608 again = False
609 for sub in words:
610 prev = new
611 new = new.eliminate_word(sub, words[sub], _all=_all, inverse=inverse)
612 if new != prev:
613 again = True
614 else:
615 while again:
616 again = False
617 for sub in words:
618 prev = new
619 new = new.eliminate_word(sub, _all=_all, inverse=inverse)
620 if new != prev:
621 again = True
622 return new
624 def eliminate_word(self, gen, by=None, _all=False, inverse=True):
625 """
626 For an associative word `self`, a subword `gen`, and an associative
627 word `by` (identity by default), return the associative word obtained by
628 replacing each occurrence of `gen` in `self` by `by`. If `_all = True`,
629 the occurrences of `gen` that may appear after the first substitution will
630 also be replaced and so on until no occurrences are found. This might not
631 always terminate (e.g. `(x).eliminate_word(x, x**2, _all=True)`).
633 Examples
634 ========
636 >>> from sympy.combinatorics import free_group
637 >>> f, x, y = free_group("x y")
638 >>> w = x**5*y*x**2*y**-4*x
639 >>> w.eliminate_word( x, x**2 )
640 x**10*y*x**4*y**-4*x**2
641 >>> w.eliminate_word( x, y**-1 )
642 y**-11
643 >>> w.eliminate_word(x**5)
644 y*x**2*y**-4*x
645 >>> w.eliminate_word(x*y, y)
646 x**4*y*x**2*y**-4*x
648 See Also
649 ========
650 substituted_word
652 """
653 if by is None:
654 by = self.group.identity
655 if self.is_independent(gen) or gen == by:
656 return self
657 if gen == self:
658 return by
659 if gen**-1 == by:
660 _all = False
661 word = self
662 l = len(gen)
664 try:
665 i = word.subword_index(gen)
666 k = 1
667 except ValueError:
668 if not inverse:
669 return word
670 try:
671 i = word.subword_index(gen**-1)
672 k = -1
673 except ValueError:
674 return word
676 word = word.subword(0, i)*by**k*word.subword(i+l, len(word)).eliminate_word(gen, by)
678 if _all:
679 return word.eliminate_word(gen, by, _all=True, inverse=inverse)
680 else:
681 return word
683 def __len__(self):
684 """
685 For an associative word `self`, returns the number of letters in it.
687 Examples
688 ========
690 >>> from sympy.combinatorics import free_group
691 >>> f, a, b = free_group("a b")
692 >>> w = a**5*b*a**2*b**-4*a
693 >>> len(w)
694 13
695 >>> len(a**17)
696 17
697 >>> len(w**0)
698 0
700 """
701 return sum(abs(j) for (i, j) in self)
703 def __eq__(self, other):
704 """
705 Two associative words are equal if they are words over the
706 same alphabet and if they are sequences of the same letters.
707 This is equivalent to saying that the external representations
708 of the words are equal.
709 There is no "universal" empty word, every alphabet has its own
710 empty word.
712 Examples
713 ========
715 >>> from sympy.combinatorics import free_group
716 >>> f, swapnil0, swapnil1 = free_group("swapnil0 swapnil1")
717 >>> f
718 <free group on the generators (swapnil0, swapnil1)>
719 >>> g, swap0, swap1 = free_group("swap0 swap1")
720 >>> g
721 <free group on the generators (swap0, swap1)>
723 >>> swapnil0 == swapnil1
724 False
725 >>> swapnil0*swapnil1 == swapnil1/swapnil1*swapnil0*swapnil1
726 True
727 >>> swapnil0*swapnil1 == swapnil1*swapnil0
728 False
729 >>> swapnil1**0 == swap0**0
730 False
732 """
733 group = self.group
734 if not isinstance(other, group.dtype):
735 return False
736 return tuple.__eq__(self, other)
738 def __lt__(self, other):
739 """
740 The ordering of associative words is defined by length and
741 lexicography (this ordering is called short-lex ordering), that
742 is, shorter words are smaller than longer words, and words of the
743 same length are compared w.r.t. the lexicographical ordering induced
744 by the ordering of generators. Generators are sorted according
745 to the order in which they were created. If the generators are
746 invertible then each generator `g` is larger than its inverse `g^{-1}`,
747 and `g^{-1}` is larger than every generator that is smaller than `g`.
749 Examples
750 ========
752 >>> from sympy.combinatorics import free_group
753 >>> f, a, b = free_group("a b")
754 >>> b < a
755 False
756 >>> a < a.inverse()
757 False
759 """
760 group = self.group
761 if not isinstance(other, group.dtype):
762 raise TypeError("only FreeGroup elements of same FreeGroup can "
763 "be compared")
764 l = len(self)
765 m = len(other)
766 # implement lenlex order
767 if l < m:
768 return True
769 elif l > m:
770 return False
771 for i in range(l):
772 a = self[i].array_form[0]
773 b = other[i].array_form[0]
774 p = group.symbols.index(a[0])
775 q = group.symbols.index(b[0])
776 if p < q:
777 return True
778 elif p > q:
779 return False
780 elif a[1] < b[1]:
781 return True
782 elif a[1] > b[1]:
783 return False
784 return False
786 def __le__(self, other):
787 return (self == other or self < other)
789 def __gt__(self, other):
790 """
792 Examples
793 ========
795 >>> from sympy.combinatorics import free_group
796 >>> f, x, y, z = free_group("x y z")
797 >>> y**2 > x**2
798 True
799 >>> y*z > z*y
800 False
801 >>> x > x.inverse()
802 True
804 """
805 group = self.group
806 if not isinstance(other, group.dtype):
807 raise TypeError("only FreeGroup elements of same FreeGroup can "
808 "be compared")
809 return not self <= other
811 def __ge__(self, other):
812 return not self < other
814 def exponent_sum(self, gen):
815 """
816 For an associative word `self` and a generator or inverse of generator
817 `gen`, ``exponent_sum`` returns the number of times `gen` appears in
818 `self` minus the number of times its inverse appears in `self`. If
819 neither `gen` nor its inverse occur in `self` then 0 is returned.
821 Examples
822 ========
824 >>> from sympy.combinatorics import free_group
825 >>> F, x, y = free_group("x, y")
826 >>> w = x**2*y**3
827 >>> w.exponent_sum(x)
828 2
829 >>> w.exponent_sum(x**-1)
830 -2
831 >>> w = x**2*y**4*x**-3
832 >>> w.exponent_sum(x)
833 -1
835 See Also
836 ========
838 generator_count
840 """
841 if len(gen) != 1:
842 raise ValueError("gen must be a generator or inverse of a generator")
843 s = gen.array_form[0]
844 return s[1]*sum([i[1] for i in self.array_form if i[0] == s[0]])
846 def generator_count(self, gen):
847 """
848 For an associative word `self` and a generator `gen`,
849 ``generator_count`` returns the multiplicity of generator
850 `gen` in `self`.
852 Examples
853 ========
855 >>> from sympy.combinatorics import free_group
856 >>> F, x, y = free_group("x, y")
857 >>> w = x**2*y**3
858 >>> w.generator_count(x)
859 2
860 >>> w = x**2*y**4*x**-3
861 >>> w.generator_count(x)
862 5
864 See Also
865 ========
867 exponent_sum
869 """
870 if len(gen) != 1 or gen.array_form[0][1] < 0:
871 raise ValueError("gen must be a generator")
872 s = gen.array_form[0]
873 return s[1]*sum([abs(i[1]) for i in self.array_form if i[0] == s[0]])
875 def subword(self, from_i, to_j, strict=True):
876 """
877 For an associative word `self` and two positive integers `from_i` and
878 `to_j`, `subword` returns the subword of `self` that begins at position
879 `from_i` and ends at `to_j - 1`, indexing is done with origin 0.
881 Examples
882 ========
884 >>> from sympy.combinatorics import free_group
885 >>> f, a, b = free_group("a b")
886 >>> w = a**5*b*a**2*b**-4*a
887 >>> w.subword(2, 6)
888 a**3*b
890 """
891 group = self.group
892 if not strict:
893 from_i = max(from_i, 0)
894 to_j = min(len(self), to_j)
895 if from_i < 0 or to_j > len(self):
896 raise ValueError("`from_i`, `to_j` must be positive and no greater than "
897 "the length of associative word")
898 if to_j <= from_i:
899 return group.identity
900 else:
901 letter_form = self.letter_form[from_i: to_j]
902 array_form = letter_form_to_array_form(letter_form, group)
903 return group.dtype(array_form)
905 def subword_index(self, word, start = 0):
906 '''
907 Find the index of `word` in `self`.
909 Examples
910 ========
912 >>> from sympy.combinatorics import free_group
913 >>> f, a, b = free_group("a b")
914 >>> w = a**2*b*a*b**3
915 >>> w.subword_index(a*b*a*b)
916 1
918 '''
919 l = len(word)
920 self_lf = self.letter_form
921 word_lf = word.letter_form
922 index = None
923 for i in range(start,len(self_lf)-l+1):
924 if self_lf[i:i+l] == word_lf:
925 index = i
926 break
927 if index is not None:
928 return index
929 else:
930 raise ValueError("The given word is not a subword of self")
932 def is_dependent(self, word):
933 """
934 Examples
935 ========
937 >>> from sympy.combinatorics import free_group
938 >>> F, x, y = free_group("x, y")
939 >>> (x**4*y**-3).is_dependent(x**4*y**-2)
940 True
941 >>> (x**2*y**-1).is_dependent(x*y)
942 False
943 >>> (x*y**2*x*y**2).is_dependent(x*y**2)
944 True
945 >>> (x**12).is_dependent(x**-4)
946 True
948 See Also
949 ========
951 is_independent
953 """
954 try:
955 return self.subword_index(word) is not None
956 except ValueError:
957 pass
958 try:
959 return self.subword_index(word**-1) is not None
960 except ValueError:
961 return False
963 def is_independent(self, word):
964 """
966 See Also
967 ========
969 is_dependent
971 """
972 return not self.is_dependent(word)
974 def contains_generators(self):
975 """
976 Examples
977 ========
979 >>> from sympy.combinatorics import free_group
980 >>> F, x, y, z = free_group("x, y, z")
981 >>> (x**2*y**-1).contains_generators()
982 {x, y}
983 >>> (x**3*z).contains_generators()
984 {x, z}
986 """
987 group = self.group
988 gens = set()
989 for syllable in self.array_form:
990 gens.add(group.dtype(((syllable[0], 1),)))
991 return set(gens)
993 def cyclic_subword(self, from_i, to_j):
994 group = self.group
995 l = len(self)
996 letter_form = self.letter_form
997 period1 = int(from_i/l)
998 if from_i >= l:
999 from_i -= l*period1
1000 to_j -= l*period1
1001 diff = to_j - from_i
1002 word = letter_form[from_i: to_j]
1003 period2 = int(to_j/l) - 1
1004 word += letter_form*period2 + letter_form[:diff-l+from_i-l*period2]
1005 word = letter_form_to_array_form(word, group)
1006 return group.dtype(word)
1008 def cyclic_conjugates(self):
1009 """Returns a words which are cyclic to the word `self`.
1011 Examples
1012 ========
1014 >>> from sympy.combinatorics import free_group
1015 >>> F, x, y = free_group("x, y")
1016 >>> w = x*y*x*y*x
1017 >>> w.cyclic_conjugates()
1018 {x*y*x**2*y, x**2*y*x*y, y*x*y*x**2, y*x**2*y*x, x*y*x*y*x}
1019 >>> s = x*y*x**2*y*x
1020 >>> s.cyclic_conjugates()
1021 {x**2*y*x**2*y, y*x**2*y*x**2, x*y*x**2*y*x}
1023 References
1024 ==========
1026 .. [1] https://planetmath.org/cyclicpermutation
1028 """
1029 return {self.cyclic_subword(i, i+len(self)) for i in range(len(self))}
1031 def is_cyclic_conjugate(self, w):
1032 """
1033 Checks whether words ``self``, ``w`` are cyclic conjugates.
1035 Examples
1036 ========
1038 >>> from sympy.combinatorics import free_group
1039 >>> F, x, y = free_group("x, y")
1040 >>> w1 = x**2*y**5
1041 >>> w2 = x*y**5*x
1042 >>> w1.is_cyclic_conjugate(w2)
1043 True
1044 >>> w3 = x**-1*y**5*x**-1
1045 >>> w3.is_cyclic_conjugate(w2)
1046 False
1048 """
1049 l1 = len(self)
1050 l2 = len(w)
1051 if l1 != l2:
1052 return False
1053 w1 = self.identity_cyclic_reduction()
1054 w2 = w.identity_cyclic_reduction()
1055 letter1 = w1.letter_form
1056 letter2 = w2.letter_form
1057 str1 = ' '.join(map(str, letter1))
1058 str2 = ' '.join(map(str, letter2))
1059 if len(str1) != len(str2):
1060 return False
1062 return str1 in str2 + ' ' + str2
1064 def number_syllables(self):
1065 """Returns the number of syllables of the associative word `self`.
1067 Examples
1068 ========
1070 >>> from sympy.combinatorics import free_group
1071 >>> f, swapnil0, swapnil1 = free_group("swapnil0 swapnil1")
1072 >>> (swapnil1**3*swapnil0*swapnil1**-1).number_syllables()
1073 3
1075 """
1076 return len(self.array_form)
1078 def exponent_syllable(self, i):
1079 """
1080 Returns the exponent of the `i`-th syllable of the associative word
1081 `self`.
1083 Examples
1084 ========
1086 >>> from sympy.combinatorics import free_group
1087 >>> f, a, b = free_group("a b")
1088 >>> w = a**5*b*a**2*b**-4*a
1089 >>> w.exponent_syllable( 2 )
1090 2
1092 """
1093 return self.array_form[i][1]
1095 def generator_syllable(self, i):
1096 """
1097 Returns the symbol of the generator that is involved in the
1098 i-th syllable of the associative word `self`.
1100 Examples
1101 ========
1103 >>> from sympy.combinatorics import free_group
1104 >>> f, a, b = free_group("a b")
1105 >>> w = a**5*b*a**2*b**-4*a
1106 >>> w.generator_syllable( 3 )
1107 b
1109 """
1110 return self.array_form[i][0]
1112 def sub_syllables(self, from_i, to_j):
1113 """
1114 `sub_syllables` returns the subword of the associative word `self` that
1115 consists of syllables from positions `from_to` to `to_j`, where
1116 `from_to` and `to_j` must be positive integers and indexing is done
1117 with origin 0.
1119 Examples
1120 ========
1122 >>> from sympy.combinatorics import free_group
1123 >>> f, a, b = free_group("a, b")
1124 >>> w = a**5*b*a**2*b**-4*a
1125 >>> w.sub_syllables(1, 2)
1126 b
1127 >>> w.sub_syllables(3, 3)
1128 <identity>
1130 """
1131 if not isinstance(from_i, int) or not isinstance(to_j, int):
1132 raise ValueError("both arguments should be integers")
1133 group = self.group
1134 if to_j <= from_i:
1135 return group.identity
1136 else:
1137 r = tuple(self.array_form[from_i: to_j])
1138 return group.dtype(r)
1140 def substituted_word(self, from_i, to_j, by):
1141 """
1142 Returns the associative word obtained by replacing the subword of
1143 `self` that begins at position `from_i` and ends at position `to_j - 1`
1144 by the associative word `by`. `from_i` and `to_j` must be positive
1145 integers, indexing is done with origin 0. In other words,
1146 `w.substituted_word(w, from_i, to_j, by)` is the product of the three
1147 words: `w.subword(0, from_i)`, `by`, and
1148 `w.subword(to_j len(w))`.
1150 See Also
1151 ========
1153 eliminate_word
1155 """
1156 lw = len(self)
1157 if from_i >= to_j or from_i > lw or to_j > lw:
1158 raise ValueError("values should be within bounds")
1160 # otherwise there are four possibilities
1162 # first if from=1 and to=lw then
1163 if from_i == 0 and to_j == lw:
1164 return by
1165 elif from_i == 0: # second if from_i=1 (and to_j < lw) then
1166 return by*self.subword(to_j, lw)
1167 elif to_j == lw: # third if to_j=1 (and from_i > 1) then
1168 return self.subword(0, from_i)*by
1169 else: # finally
1170 return self.subword(0, from_i)*by*self.subword(to_j, lw)
1172 def is_cyclically_reduced(self):
1173 r"""Returns whether the word is cyclically reduced or not.
1174 A word is cyclically reduced if by forming the cycle of the
1175 word, the word is not reduced, i.e a word w = `a_1 ... a_n`
1176 is called cyclically reduced if `a_1 \ne a_n^{-1}`.
1178 Examples
1179 ========
1181 >>> from sympy.combinatorics import free_group
1182 >>> F, x, y = free_group("x, y")
1183 >>> (x**2*y**-1*x**-1).is_cyclically_reduced()
1184 False
1185 >>> (y*x**2*y**2).is_cyclically_reduced()
1186 True
1188 """
1189 if not self:
1190 return True
1191 return self[0] != self[-1]**-1
1193 def identity_cyclic_reduction(self):
1194 """Return a unique cyclically reduced version of the word.
1196 Examples
1197 ========
1199 >>> from sympy.combinatorics import free_group
1200 >>> F, x, y = free_group("x, y")
1201 >>> (x**2*y**2*x**-1).identity_cyclic_reduction()
1202 x*y**2
1203 >>> (x**-3*y**-1*x**5).identity_cyclic_reduction()
1204 x**2*y**-1
1206 References
1207 ==========
1209 .. [1] https://planetmath.org/cyclicallyreduced
1211 """
1212 word = self.copy()
1213 group = self.group
1214 while not word.is_cyclically_reduced():
1215 exp1 = word.exponent_syllable(0)
1216 exp2 = word.exponent_syllable(-1)
1217 r = exp1 + exp2
1218 if r == 0:
1219 rep = word.array_form[1: word.number_syllables() - 1]
1220 else:
1221 rep = ((word.generator_syllable(0), exp1 + exp2),) + \
1222 word.array_form[1: word.number_syllables() - 1]
1223 word = group.dtype(rep)
1224 return word
1226 def cyclic_reduction(self, removed=False):
1227 """Return a cyclically reduced version of the word. Unlike
1228 `identity_cyclic_reduction`, this will not cyclically permute
1229 the reduced word - just remove the "unreduced" bits on either
1230 side of it. Compare the examples with those of
1231 `identity_cyclic_reduction`.
1233 When `removed` is `True`, return a tuple `(word, r)` where
1234 self `r` is such that before the reduction the word was either
1235 `r*word*r**-1`.
1237 Examples
1238 ========
1240 >>> from sympy.combinatorics import free_group
1241 >>> F, x, y = free_group("x, y")
1242 >>> (x**2*y**2*x**-1).cyclic_reduction()
1243 x*y**2
1244 >>> (x**-3*y**-1*x**5).cyclic_reduction()
1245 y**-1*x**2
1246 >>> (x**-3*y**-1*x**5).cyclic_reduction(removed=True)
1247 (y**-1*x**2, x**-3)
1249 """
1250 word = self.copy()
1251 g = self.group.identity
1252 while not word.is_cyclically_reduced():
1253 exp1 = abs(word.exponent_syllable(0))
1254 exp2 = abs(word.exponent_syllable(-1))
1255 exp = min(exp1, exp2)
1256 start = word[0]**abs(exp)
1257 end = word[-1]**abs(exp)
1258 word = start**-1*word*end**-1
1259 g = g*start
1260 if removed:
1261 return word, g
1262 return word
1264 def power_of(self, other):
1265 '''
1266 Check if `self == other**n` for some integer n.
1268 Examples
1269 ========
1271 >>> from sympy.combinatorics import free_group
1272 >>> F, x, y = free_group("x, y")
1273 >>> ((x*y)**2).power_of(x*y)
1274 True
1275 >>> (x**-3*y**-2*x**3).power_of(x**-3*y*x**3)
1276 True
1278 '''
1279 if self.is_identity:
1280 return True
1282 l = len(other)
1283 if l == 1:
1284 # self has to be a power of one generator
1285 gens = self.contains_generators()
1286 s = other in gens or other**-1 in gens
1287 return len(gens) == 1 and s
1289 # if self is not cyclically reduced and it is a power of other,
1290 # other isn't cyclically reduced and the parts removed during
1291 # their reduction must be equal
1292 reduced, r1 = self.cyclic_reduction(removed=True)
1293 if not r1.is_identity:
1294 other, r2 = other.cyclic_reduction(removed=True)
1295 if r1 == r2:
1296 return reduced.power_of(other)
1297 return False
1299 if len(self) < l or len(self) % l:
1300 return False
1302 prefix = self.subword(0, l)
1303 if prefix == other or prefix**-1 == other:
1304 rest = self.subword(l, len(self))
1305 return rest.power_of(other)
1306 return False
1309def letter_form_to_array_form(array_form, group):
1310 """
1311 This method converts a list given with possible repetitions of elements in
1312 it. It returns a new list such that repetitions of consecutive elements is
1313 removed and replace with a tuple element of size two such that the first
1314 index contains `value` and the second index contains the number of
1315 consecutive repetitions of `value`.
1317 """
1318 a = list(array_form[:])
1319 new_array = []
1320 n = 1
1321 symbols = group.symbols
1322 for i in range(len(a)):
1323 if i == len(a) - 1:
1324 if a[i] == a[i - 1]:
1325 if (-a[i]) in symbols:
1326 new_array.append((-a[i], -n))
1327 else:
1328 new_array.append((a[i], n))
1329 else:
1330 if (-a[i]) in symbols:
1331 new_array.append((-a[i], -1))
1332 else:
1333 new_array.append((a[i], 1))
1334 return new_array
1335 elif a[i] == a[i + 1]:
1336 n += 1
1337 else:
1338 if (-a[i]) in symbols:
1339 new_array.append((-a[i], -n))
1340 else:
1341 new_array.append((a[i], n))
1342 n = 1
1345def zero_mul_simp(l, index):
1346 """Used to combine two reduced words."""
1347 while index >=0 and index < len(l) - 1 and l[index][0] == l[index + 1][0]:
1348 exp = l[index][1] + l[index + 1][1]
1349 base = l[index][0]
1350 l[index] = (base, exp)
1351 del l[index + 1]
1352 if l[index][1] == 0:
1353 del l[index]
1354 index -= 1