Инвертирующие перестановки в 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

Возможно, есть кратчайший путь:

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 3

Версия "функциональный стиль":

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

По существу, сортировка индексов i перестановки по их значениям j в перестановке дает желаемое обратное значение.

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

Исправьте меня, если я ошибаюсь, но я думаю, что проблема с моим кодом возникает, когда я заменяю str на список: str - это строка, а list(str) - это список строковых элементов. Однако, поскольку строковые элементы не могут быть численно сопоставлены с числами, код не может дать результат (кроме []).

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)