# How to find a permutation which sends a given list to another given list in SageMath?

Given two list L1, L2, say

L1=[1,2,5,6,3,4,4,8,2,1,9,3,2]
L2=[1,2,2,5,6,4,3,4,8,9,1,2,3]


How to find a permutation w in $S_{13}$ such that w(L1) = L2 in python?

Here $w=s_{i_1} \cdots s_{i_k}$ for some $k$, and each $s_{j}$ acts on L1 by exchanging the jth and j+1th element of L1.

Thank you very much.

edit retag close merge delete

I doubt that there is a built-in function for this since the data don't give a single well-defined permutation — since L1 and L2 are multisets, there are choices. What have you tried?

( 2022-01-23 18:39:54 +0200 )edit

What is the relevance of the sentence "Here $s_i$ is ..."?

( 2022-01-23 18:49:16 +0200 )edit

@John, thank you very much for your comments. I have edited the post.

( 2022-01-23 18:59:24 +0200 )edit

@John, the result of $w$ is not unique. There is at least one $w$. I only need one $w$ such that $w(L1)=L2$. The only method I know is to check each $w$ in $S_{13}$ and to see if $w(L1)=L2$. But it will take a very long time if $n$ in $S_n$ is large.

( 2022-01-23 19:02:19 +0200 )edit

@John, $L1$ and $L2$ are lists. There could be repetition of elements in $L1$, $L2$. The numbers of occurrences of each $i$ in $L1$, $L2$ are the same. For example, $L1=[1,1,3]$, $L2=[1,3,1]$. Then we can take $w = s_2$.

( 2022-01-23 19:04:10 +0200 )edit

Sort by » oldest newest most voted

Solution via indirect sorting:

L1=[1,2,5,6,3,4,4,8,2,1,9,3,2]
L2=[1,2,2,5,6,4,3,4,8,9,1,2,3]
perm = Word(L2).standard_permutation() / Word(L1).standard_permutation()
assert [L1[i-1] for i in perm] == L2
print(perm)

more

@max, thank you very much!

( 2022-01-24 08:21:56 +0200 )edit

I think this code should work: first construct a list with the one-line form for the permutation, then convert it to a permutation:

def find_permutation(L1, L2):
oneline = []
for n in L1:
# Look for n in L2.
# Sage's one-line permutation format expects indices to start at 1, not 0,
# so add 1 to all indices here.
j = L2.index(n) + 1
# If we've already found this instance, look in the rest of the list for another one.
while j in oneline:
j += L2[j:].index(n) + 1
oneline.append(j)
return oneline

Permutation(find_permutation(L1, L2))

more

@John, thank you very much!

( 2022-01-24 08:21:41 +0200 )edit