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.
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)
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))
Asked: 2022-01-23 15:17:09 +0100
Seen: 866 times
Last updated: Jan 23 '22
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
I doubt that there is a built-in function for this since the data don't give a single well-defined permutation — since
L1andL2are multisets, there are choices. What have you tried?What is the relevance of the sentence "Here $s_i$ is ..."?
@John, thank you very much for your comments. I have edited the post.
@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.
@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$.