Это «проблема ладьи», которую можно сформулировать следующим образом:
Подсчитайте количество способов, которыми вы можете поместить N ладей (назначение) в данное подмножество (1 с в матрице). ) доски N x N, так что никакие две ладьи не могут атаковать друг друга (что обеспечивает соответствие 1-1 между студентами и темами)
Существует много написанного о проблемах ладьи, которые вы можетенайдите, прибегая к помощи этих слов.
В этом конкретном случае есть довольно простое решение для динамического программирования:
Пусть C будет набором всех столбцов в матрице.
Учитывая подмножество S из C , пусть COUNT (S) будет количеством способов размещения не атакующих ладей именно в этих столбцах. , в первых | S | строках.
COUNT (C) - вот ответ, который вы ищете - количество назначений для всей доски.
COUNT (S) легко рассчитывается по подсчетам для меньших подмножеств столбцов. Если столбец c является последним размещенным в строке | S | , то существует COUNT (Sc) способов, которыми грачи в других рядах могутбыть организованным. Просто сложите счетчики для всех <= | S | </strong> вариантов c , соответствующих 1 с в строке | S | .
Связанное решение представляет каждый набор S в виде битовой маски и рассчитывает количество для каждого набора в числовом порядке. Поскольку каждый Sc соответствует меньшему числу, чем S , подмножества, необходимые для каждого нового подмножества, будут вычислены первыми.