Эффективное вычисление набора сюръективных функций ⇐ Python

[Anonymous]

Функция f : X -> Y является сюръективной, если каждый элемент Y имеет хотя бы один прообраз в X. Когда X = {0,...,m-1} и Y = {0,...,n-1} являются двумя конечными множествами, тогда f соответствует кортежу m чисел < n, и он является сюръективным именно тогда, когда каждое число < n появляется в не реже одного раза. (Когда мы требуем, чтобы каждое число появлялось ровно один раз, у нас есть n=m и перестановки.)

Я хотел бы знать эффективный алгоритм для вычисления набора всех сюръективных кортежей для двух заданных чисел n и m, как указано выше. Количество этих кортежей можно очень эффективно вычислить с помощью включения-исключения (см., например, здесь), но я не думаю, что это полезно здесь (поскольку мы сначала вычислим все кортежи , а затем шаг за шагом удаляем несюръективные кортежи, и я предполагаю, что вычисление всех кортежей займет больше времени.). Другой подход заключается в следующем:

Рассмотрим, например, кортеж

(1,6,4,2,1,6,0,2,5,1,3,2,3)

в котором каждое число < 7 встречается хотя бы один раз. Посмотрите на самый большой номер и сотри его:

(1,*,4,2,1,*,0,2,5,1,3,2,3)

Он появляется в индексах 1 и 5, поэтому соответствует набору {1,5}, подмножеству индексов. Остальное соответствует кортежу

(1,4,2,1,0,2,5,1,3,2,3)

со свойством, что каждое число < 6 встречается хотя бы один раз.

Мы видим, что сюръективные m-кортежи чисел < n соответствуют парам (T,a), где T — непустое подмножество {0,...,m-1}, а a — сюръективное (m-k)-кортеж чисел < n-1, где T содержит k элементов.

Это приводит к следующей рекурсивной реализации (написанной на Python):

импортировать инструменты itertools def surjective_tuples(m: int, n: int) -> set[tuple]: """Набор всех m-кортежей чисел < n, где каждое число < n встречается хотя бы один раз. Аргументы: м: длина кортежа n: количество различных значений """ если n == 0: вернуть set(), если m > 0, иначе {()} если n > m: вернуть набор() результат = установить() для k в диапазоне (1, m + 1): less_tuples = surjective_tuples(m - k, n - 1) подмножества = itertools.combinations(диапазон(m), k) для подмножества в подмножествах: для small_tuple в small_tuples: мой_тупле = [] количество = 0 для меня в диапазоне (м): если я в подмножестве: my_tuple.append(n - 1) считать += 1 еще: my_tuple.append(smaller_tuple) result.add(кортеж(my_tuple)) вернуть результат Однако я заметил, что это происходит довольно медленно, когда входные числа большие. Подозреваю, что есть более быстрый алгоритм.