Ask Your Question
0

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

asked 2022-01-23 15:17:09 +0200

lijr07 gravatar image

updated 2022-01-23 20:14:34 +0200

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 flag offensive close merge delete

Comments

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?

John Palmieri gravatar imageJohn Palmieri ( 2022-01-23 18:39:54 +0200 )edit

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

John Palmieri gravatar imageJohn Palmieri ( 2022-01-23 18:49:16 +0200 )edit

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

lijr07 gravatar imagelijr07 ( 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.

lijr07 gravatar imagelijr07 ( 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$.

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

2 Answers

Sort by » oldest newest most voted
2

answered 2022-01-23 20:43:59 +0200

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))
edit flag offensive delete link more

Comments

@John, thank you very much!

lijr07 gravatar imagelijr07 ( 2022-01-24 08:21:41 +0200 )edit
2

answered 2022-01-23 22:33:06 +0200

Max Alekseyev gravatar image

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)
edit flag offensive delete link more

Comments

@max, thank you very much!

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-01-23 15:17:09 +0200

Seen: 63 times

Last updated: Jan 23