【python】数组的序列变换？

题目:给定数组A = {1, 2, 3, 4, 5, 6}，并给定一个变换序列P = {3, 1, 5, 4, 0, 2},将变换序列应用到数组A上，得到新的数组B = {A[3], A[1], A[5], A[4], A[0],A[2]} = {4， 2， 6， 5， 1， 3}。

分析：对于A[i]，如果P[0...i-1]中，比P[i]大的元素是k，那么A[i]就向右移动了k位。

code：

def relocate(i):

    change = P[i]

    k = 0

    j = 0

    # 检测A[0...i - 1]中有几个元素比P[i]大

    while j < i:

        if P[j] > change:

            k += 1

        j += 1

    return change + k

def makeShift(begin, end):

    # 把A[begin, end]之间的元素向右边挪动一位

    i = end

    while i > begin:

        A[i] = A[i - 1]

        i -= 1

def doPermutation(A):

    for i in range(len(A)):

        # 计算A[i]右移后的位置

        change = relocate(i)

        temp = A[change]

        makeShift(i, change)

        A[i] = temp

    return A

if __name__ == "__main__":

    A = [1, 2, 3, 4, 5, 6]

    P = [3, 1, 5, 4, 0, 2]

    print(doPermutation(A))

程序运行结果:

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