Python, перестановка в функцию индекса перестановки

Question

У меня есть несколько перестановок списка:

>>> import itertools
>>> perms = list(itertools.permutations([0,1,2,3]))
>>> perms
[(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (1, 0, 2, 3), (1, 0, 3, 2), (1, 2, 0, 3), (1, 2, 3, 0), (1, 3, 0, 2), (1, 3, 2, 0), (2, 0, 1, 3), (2, 0, 3, 1), (2, 1, 0, 3), (2, 1, 3, 0), (2, 3, 0, 1), (2, 3, 1, 0), (3, 0, 1, 2), (3, 0, 2, 1), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 0, 1), (3, 2, 1, 0)]
>>> len(perms)
24

Какую функцию я могу использовать (без доступа к списку perm), чтобы получить индекс произвольной перестановки, например (0, 2, 3, 1) -> 3?

(Вы можете предположить, что переставленные элементы всегда представляют собой восходящий список целых чисел, начиная с нуля.)

Подсказка: может быть задействована факториальная система счисления. https://en.wikipedia.org/wiki/Factorial_number_system

Answer 1

Внезапно я придумал следующее, но не тестировал его полностью.

from math import factorial
elements = list(range(4))
permutation = (3, 2, 1, 0)
index = 0
nf = factorial(len(elements))

for n in permutation:
    nf //= len(elements)
    index += elements.index(n) * nf
    elements.remove(n)

print(index)

EDIT: заменил nf /= len(elements) на nf //= len(elements)

Answer 2

Полагаю, это вызов, поэтому вот мой (рекурсивный) ответ:

import math
import itertools

def get_index(l):
    # In a real function, there should be more tests to validate that the input is valid, e.g. len(l)>0
    # Terminal case
    if len(l)==1:
        return 0

    # Number of possible permutations starting with l[0]
    span = math.factorial(len(l)-1)

    # Slightly modifying l[1:] to use the function recursively
    new_l = [ val if val < l[0] else val-1 for val in l[1:] ]

    # Actual solution
    return get_index(new_l) + span*l[0]


get_index((0,1,2,3))
# 0
get_index((0,2,3,1))
# 3
get_index((3,2,1,0))
# 23
get_index((4,2,0,1,5,3))
# 529
list(itertools.permutations((0,1,2,3,4,5))).index((4,2,0,1,5,3))
# 529

Answer 3

from math import factorial

def perm_to_permidx(perm):
    # Extract info
    n = len(perm)
    elements = range(n)
    # "Gone"s will be the elements of the given perm
    gones = []
    # According to each number in perm, we add the repsective offsets
    offset = 0
    for i, num in enumerate(perm[:-1], start=1):
        idx = num - sum(num > gone for gone in gones)
        offset += idx * factorial(n - i)
        gones.append(num)
    return offset

the_perm = (0, 2, 3, 1)
print(perm_to_permidx(the_perm))
# 3

Объяснение: Все перестановки данного диапазона можно рассматривать как группы перестановок. Так, например, для перестановок 0, 1, 2, 3 мы сначала «фиксируем» 0 и переставляем отдых, затем исправляем 1 и переставляем отдых, и так далее. Как только мы зафиксируем число, остальное снова будет перестановками; поэтому мы снова фиксируем число за раз из оставшихся чисел и переставляем остальные. Это продолжается до тех пор, пока у нас не останется только один номер. Каждому уровню исправления соответствует (n-i)! перестановок.

Таким образом, этот код находит «смещения» для каждого уровня перестановки. offset соответствует тому месту, где начинается данная перестановка, когда мы фиксируем числа perm по порядку. Для данного примера (0, 2, 3, 1) мы сначала смотрим на первое число в данном perm, которое равно 0, и считаем смещение равным 0. Затем это переходит в список gones (мы увидим его использование). Затем, на следующем уровне перестановки, мы видим 2 как фиксирующее число. Чтобы вычислить смещение для этого, нам нужен «порядок» этих 2 среди остальных трех чисел. Здесь в игру вступает gones; если уже фиксированное и рассматриваемое число (в данном случае 0) меньше текущего фиксатора, мы вычитаем 1, чтобы найти новый порядок. Затем рассчитывается и накапливается смещение. Для следующего номера 3 новый порядок 3 - (1 + 1) = 1, потому что оба предыдущих фиксатора 0 и 2 находятся «слева» от 3.

Это продолжается до последнего номера данного perm, так как там нет необходимости смотреть на это; он все равно будет определен.

Answer 4

Вам нужно написать свою функцию. Что-то вроде этого будет работать

import math

def perm_loc(P):

    N = len(P)
    assert set(P) == set(range(N))

    def rec(perm):
        nums = set(perm)
        if not perm:
            return 0
        else:
            sub_res = rec(perm[1:])                  # Result for tail of permutation
            sub_size = math.factorial(len(nums) - 1) # How many tail permutations exist
            sub_index = sorted(nums).index(perm[0])  # Location of first element in permutaiotn
                                                     # in the sorted list of number
            return sub_index * sub_size + sub_res

    return rec(P)

Всю работу выполняет функция rec, с perm_lo c, которая просто служит оболочкой вокруг нее. Обратите внимание, что этот алгоритм основан на природе алгоритма перестановки, который использует itertools.permutation.

Следующий код проверяет вышеуказанную функцию. Сначала на вашем образце, а затем на всех перестановках range(7):

print perm_loc([0,2,3,1]) # Print the result from the example

import itertools

def test(N):
    correct = 0
    perms = list(itertools.permutations(range(N)))
    for (i, p) in enumerate(perms):
        pl = perm_loc(p)
        if i == pl:
            correct += 1
        else:
            print ":: Incorrect", p, perms.index(p), perm_loc(N, p)
    print ":: Found %d correct results" % correct

test(7) # Test on all permutations of range(7)