Как рассчитать эффективный способ перестановки мультимножеств в Python

Question

Я смотрю, чтобы узнать, является ли встроенная в математическую библиотеку в Python встроенная переменная «Перестановка мультимножеств».

Я знаю, что это можно запрограммировать, но на данный момент я не эксперт по Python.Так что я не могу сделать сложным образом.Есть ли здесь кто-нибудь, кто может?

https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets

У меня были проблемы с программированием (я не студент, но я хочу улучшитья сам), но мое решение недостаточно быстрое (во многих тестовых случаях время ожидания истекло).Но проблема звучит просто: сколько путей выходит из верхнего левого угла в нижний правый в матрице, если вы можете только шагать вправо и вниз. Я действительно не хочу, чтобы кто-то решал вместо меня. Мне просто нужен совет.Я попробовал матрицу Паскаля, которая работает, но медленно.Я думаю, что «Перестановка мультимножества» является моим решением, потому что есть два типа шагов D, R, если моя матрица MxN (1 ≤ M, N ≤ 106), что означает D M-1 и R N-1 ступень: n = N + M-2, m1 = M-1, м2 = N-1

Answer 1

Обратите внимание, что у вас неправильная начальная настройка, поэтому вам здесь действительно не нужны перестановки мультимножеств.

проблема звучит легко: сколько путей выходит из верхнего левого в внизу справа в матрице, если вы можете только шагать вправо и вниз

Последовательность элементарных ходов для матрицы NxM содержит ровно N ходов вниз и M ходов вправо. Есть C(N+M, M) (nCr, комбинаций число, биномиальный коэффициент ) способов сделать такую ​​последовательность.

В реализации Python для вычисления значения nCr из второй ссылки (я добавил целочисленное деление) используется довольно оптимальный алгоритм - он сводит к минимуму количество шагов, выбирая правильные k, и избегает слишком больших промежуточных значений из-за одновременного умножения и деления. Обратите внимание, что для вашего случая аргументы n = N+M и k = M

def binomialCoefficient(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    k = min(k, n - k) # take advantage of symmetry
    c = 1
    for i in range(k):
        c = c * (n - i) // (i + 1)
    return c

Для генерации самих путей (при необходимости) рассмотрим itertools.combinations

Answer 2

Вы можете использовать функцию permutations () из itertools, чтобы получить все перестановки и набор для пропуска повторений.

from itertools import permutations

multiset = "MISSISSIPPI"
perms = iter(p for s in [set()] for p in permutations(multiset) if p not in s and not s.add(p))

count = 0
for p in perms:
    count += 1
print(count) # 34650

Если вам нужно только подсчитать, вы можете реализовать формулу (с небольшой помощью из математики и сборников):

from collections import Counter
from math import factorial

def multisetPermutations(A):
    result = factorial(len(A))
    for m in Counter(A).values():
        result = result // factorial(m)
    return result

print(multisetPermutations("MISSISSIPPI")) # 34650