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 S13 such that w(L1) = L2 in python?
Here w=si1⋯sik for some k, and each sj 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: 3 years ago
Seen: 1,275 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 si 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 S13 and to see if w(L1)=L2. But it will take a very long time if n in Sn 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=s2.