在Python中反转排列

Question

我是编程的新手，我正在尝试使用以下代码编写一个Python函数来查找{1,2,3，...，n}上的置换的逆矩阵：

def inv(str):
    result = []
    i = list(str).index(min(list(str)))
    while min(list(str)) < len(list(str)) + 1:
        list(str)[i : i + 1] = [len(list(str)) + 1]
        result.append(i + 1)
    return result

但是，当我尝试使用该函数时，inv('<mypermutation>')返回[]。我错过了什么吗？ Python是否因为某些语法原因跳过了我的while循环而我不明白？我的google和stackoverflow都没有搜索我认为有用的主题。

Answer 1

如果您只想要反向排列，则可以使用

def inv(perm):
    inverse = [0] * len(perm)
    for i, p in enumerate(perm):
        inverse[p] = i
    return inverse

perm = [3, 0, 2, 1]
print(inv(perm))
for i in perm:
    print(inv(perm)[i])

[1, 3, 2, 0]
0
1
2
3

Answer 2

如果我有这个错误，请纠正我，但我认为当我将str更改为列表时，我的代码会出现问题：str是一个字符串，而list(str)是一个字符串元素列表。但是，由于字符串元素无法在数字上与数字进行比较，因此代码无法生成结果（[]除外）。

Answer 3

“功能风格”版本：

def invert_permutation(permutation):
    return [i for i, j in sorted(enumerate(permutation), key=lambda (_, j): j)]

基本上，在置换中通过它们的值j对置换的索引i进行排序产生期望的逆。

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

invert_permutation(p)
# [3, 1, 0, 5, 4, 2]

# inverse of inverse = identity
invert_permutation(invert_permutation(p)) == p
# True

Answer 4

也许有一个最短的方式：

def invert(p):
    return [p.index(l) for l in range(len(p))] 

以便：

perm = [3, 0, 2, 1]; print(invert(perm))

回报

[1,3,2,0]

Answer 5

其他答案是正确的，但是对于它的价值，使用numpy有一个更高效的替代方案：

inverse_perm = np.arange(len(permutation))[np.argsort(permutation)]

时间码：

def invert_permutation_list_scan(p):
    return [p.index(l) for l in range(len(p))]

def invert_permutation_list_comp(permutation):
    return [i for i, j in sorted(enumerate(permutation), key=lambda i_j: i_j[1])]

def invert_permutation_numpy(permutation):
    return np.arange(len(permutation))[np.argsort(permutation)] 

x = np.random.randn(10000)
perm = np.argsort(x)
permlist = list(perm)
assert np.array_equal(invert_permutation_list_scan(permlist), invert_permutation_numpy(perm))
assert np.array_equal(invert_permutation_list_comp(perm), invert_permutation_numpy(perm))
%timeit invert_permutation_list_scan(permlist)
%timeit invert_permutation_list_comp(perm)
%timeit invert_permutation_numpy(perm)

结果：

7.16 s ± 109 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
6.18 ms ± 45.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
524 µs ± 8.93 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)