Permutation documentation question

[Alexander Ness]

Hi everyone,

I've been experimenting with the "Permutations" module, trying to follow the examples in the documentation here:

https://docs.sympy.org/latest/modules/combinatorics/permutations.html

As expected,

Permutation(1, 2)(2, 3) == Permutation(1, 2) * Permutation(2, 3)

But doesn't this mean that the permutations are applied from left to right, since (as described in the docs) left-to-right permutation multiplication p*q is equivalent to composition q o p?

If so, this contradicts the documentation's claim that "The convention is that the permutations are applied from right to left".

If not, I must be confused about something, and would appreciate any corrections.

Thanks for your help,

Alex

[Chris Smith]

Given elements `0,1,2,3`, `Permutation(1,2)(2,3)` interpreting R to L gives `0123->0132->0312`; interpreting L to R gives `0123->0213->0231`

If you let `p = Permutation(1,2)(2,3)` then `p.list()` gives `[0, 3, 1, 2]` which is consistent with R to L interpretation. So the assumption that spelling it `Permutation(1,2)*Permutation(2,3)` means left to right must be wrong?

/c

[Chris Smith]

So documentation here, "The composite of two permutations p*q means first apply p, then q" should read "...apply q, then p", right? This would be an easy issue to open and fix if there is consensus that it is wrong as written. But note that using the composition of function syntax reverses the order, "One can use also the notation p(i) = i^p, but then the composition rule is (p*q)(i) = q(p(i)), not p(q(i)):"

/c

[Alexander Ness]

Hi Chris,

Thanks for your response.  When you write,

> If you let `p = Permutation(1,2)(2,3)` then `p.list()` gives `[0, 3, 1, 2]` which is consistent with R to L interpretation

I think this is incorrect (and I contend that the docs are incorrect on this point as well).

Multiplying the transpositions (1,2)(2,3) from R to L, we end up with the cycle (1,2,3),

which in list form is [0, 2, 3, 1] (if `p.list()` is the second line of 2-line permutation notation).

What do you think?

--
You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/5MTQFwB7xIo/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sympy+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/7556df78-eb14-408c-bf38-326dafaa1318n%40googlegroups.com.

[Chris Smith]

My thinking is expression in the transformations of the original list of items, [0,1,2,3]. If you first transpose the 2nd and third position you get [0,1,3,2] and then if you transpose 1st and 2nd position you get [0,3,1,2]. You'll see my name all over the docs for that module so if you can find the error in my thinking here, you are close to the source ;-)

/c

[Alexander Ness]

Hi Chris,

The convention that I'm familiar with is that the notation (both cycle notation and the two-line notation) represents the exchange of elements, not positions.  See for example

http://www.math.caltech.edu/~2015-16/1term/ma006a/17.%20More%20permutations.pdf

pp. 4--5.

So my interpretation of t*s where t=(1,2) and s=(2,3) (multiplying from R to L) would be:

1 -s-> 1 -t-> 2

2 -s-> 3 -t-> 3

3 -s-> 2 -t-> 1,

hence (1,2,3) ("1 goes to 2, 2 goes to 3, 3 goes to 1"), or (in list form) [0, 2, 3, 1].

Is transposition of elements from right to left (my interpretation) equivalent to transposition of positions from left to right (your interpretation)?  I can't think of any counterexamples, but I'll chew on it.

At the very least, I think that just specifying a multiplication direction without specifying what's being permuted (elements or positions) is ambiguous.

Thanks again,

Alex

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/b0302a20-7afa-48e7-ac63-2f467c0b164cn%40googlegroups.com.

[Aaron Meurer]

If you have the list [1, 2, 3] and you permute positions 2 and 3, you
get [1, 3, 2], then permuting positions 1 and 2 gives [3, 1, 2].

>>> list(Permutation(1, 2)(2, 3))
[0, 3, 1, 2]

(the 0 is also included because Permutation assumes 0 indexing). Note
the distinction between the permutation, written in cycle notation,
and the permuted list. The permutation (1 2)(2 3) is equal to the
permutation (1 3 2)

>>> Permutation(1, 2)(2, 3)
Permutation(1, 3, 2)

This means the first element becomes the 3rd, the third element
becomes 2nd, and the second element becomes 1st.

The distinction is confusing because we use the numbers 0, 1, 2, 3 for
both. It may help to instead think of permuting the list ['a', 'b',
'c', 'd'].

>>> Permutation(1, 2)(2, 3)(['a', 'b', 'c', 'd'])
['a', 'd', 'b', 'c']

The right-to-left applies to the application of a permutation to a sequence:

>>> Permutation(2, 3)(['a', 'b', 'c', 'd'])
['a', 'b', 'd', 'c']
>>> Permutation(1, 2, size=4)(Permutation(2, 3)(['a', 'b', 'c', 'd']))
['a', 'd', 'b', 'c']

When Permutation is called with a single number, it returns what that
numeric index is mapped to

>>> Permutation(1, 2)(1)
2
>>> Permutation(1, 2)(2)
1

On Fri, Mar 12, 2021 at 11:15 AM Alexander Ness <asn...@gmail.com> wrote:
>
> Hi Chris,
>
> The convention that I'm familiar with is that the notation (both cycle notation and the two-line notation) represents the exchange of elements, not positions. See for example

As I pointed out above, I believe this is really the source of the
confusion here. There is a distinction between permutation itself,
written in cycle notation, and the list itself. Unfortunately, the
examples use 1..n (or 0..n-1) for both, which can be confusing. It may
be easier to show the permutation of a list of Symbols, so that it's
clearer that a number represents the index in the permutation itself,
and a symbol represents a permuted element of a list.

I've read through the docs a couple of times, but I can't tell if they
are wrong or just confusing. Either way, I would suggest
disambiguation using the above suggestion or something similar. Using
the same notation (__call__) for both composition and application of a
permutation may also have been a mistake, but I'm not sure what we can
do about that.


Aaron Meurer

> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CABL__Ev9SUwgCsy4irD7gC5XCxQSCHD2FUwN7L%2BPjLNfsxerSA%40mail.gmail.com.

[Chris Smith]

From page two of the notes I reconstruct the same output

`

>>> (Permutation(1,5)(2,6,4)).list()

[0, 5, 6, 3, 2, 1, 4]

`

Could it be that the semantics (which are the same when you start with an ordered list and do only one cycle) are the confusing issue in that you thought it meant elements but it really refers to position?

/c

[Chris Smith]

...but then I see in the notes "decomposing a cycle" where the author is definitely referring to elements being switched. But it makes sense to me to make the references refer to position so they can be applied regardless of the identity of the elements (as in Aaron's example using a string). This might be something to make clear at the outset of the Permutation documentation.

If you are more comfortable working with swaps in the order given you can write a utility function something like this:

```

def eswap(*p):

 assert len(p)%2==0

 big = max(p)

 rv = list(range(big+1))

 for i,j in zip(p[::2],p[1::2]):

     k,l = [rv.index(w) for w in (i,j)]

     rv[k], rv[l] = rv[l],rv[k]

 return Permutation(rv)

>>> eswap(1,3,1,2)

(132)

>>> eswap(1,2,1,3)

(123)

```

/c

[Alexander Ness]

Hi again,

Note also that GAP handles permutations identically to SymPy, and the manual states unambiguously that "GAP multiplies permutations from left to right!":

https://college.cengage.com/mathematics/gallian/abstract_algebra/5e/shared/gap/gap_manual.pdf?URL=www.kau.edu.sa

(p. 25).

Again, this follows the conventional element interpretation, rather than the position interpretation.  I understand the arguments in favor of the position interpretation, but I would encourage you to adopt the convention that, as far as I can tell, is in wider use.

Thanks,

Alex

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/05b31174-bc37-45ed-8a34-bc69b636cc10n%40googlegroups.com.

[Chris Smith]

I'm sure that changing the convention would be greatly frowned upon. The SymPy documentation clearly states

```
Caution: when the cycles have common elements

between them then the order in which the

permutations are applied matters. The

convention is that the permutations are

applied from *right to left*. In the following, the

transposition of elements 2 and 3 is followed

by the transposition of elements 1 and 2:



>>> Permutation(1, 2)(2, 3) == Permutation([(1, 2), (2, 3)])

True

>>> Permutation(1, 2)(2, 3).list()

[0, 3, 1, 2]



If the first and second elements had been

swapped first, followed by the swapping of the second

and third, the result would have been [0, 2, 3, 1].

If, for some reason, you want to apply the cycles

in the order they are entered, you can simply reverse

the order of cycles:



>>> Permutation([(1, 2), (2, 3)][::-1]).list()

[0, 2, 3, 1]
```

But the matter of fixing the docs to reflect that `p*q` means `q` is applied first and then `p` still remains to be fixed. This should be opened as an issue.

/c