Сложные комбинаторные алгоритмы

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

• Вычислить общее количество комбинации, обычно прямые умножение вариантов как изложенного в вашем вопросе будет достаточно. Нет необходимости хранить все это комбинаций.
• Затем разделите вашу сумму на исключения. Исключения могут быть хранится как набор правил, эффективно говоря, какие комбинации не допускаются.
• Чтобы выработать общее количество combinations allowable, you will have to run through the entire set of exception rules.

If you think of all your combinations as a set, then the exceptions just remove members of that set. But you don't need to store the entire set, just the exceptions, since you can calculate the size of the set quite easily.

Завод HP по производству высокопроизводительных серверов в Калифорнии много лет использовал для этого систему, основанную на индивидуальных правилах.

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

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

Студент, изучающий информатику, имеющий опыт работы с компиляторами, узнал бы код. Код проанализировал спецификацию, внутреннее создание многопоточного дерева частей, сгруппированных по типу. Затем он применил правила к внутреннему дереву, чтобы определить, соответствует ли порядок.

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

« Генерирующие функции » приходит на ум как одна конструкция, которую можно использовать при решении задач этого типа. Я хотел бы отметить, что существует несколько различных генерирующих функций в зависимости от того, что вы хотите.

В Северной Америке автомобильные номерные знаки могут быть интересной комбинаторной проблемой при подсчете всех перестановок, где есть 36 возможных значений для каждого места из 6 или 7, которые являются длинами номерных знаков в зависимости от того, где они получают номер. Однако некоторые комбинации не принимаются из-за того, что в некоторых из них есть нецензурные или расистские слова, что немного усложняет задачу. Например, есть позорное N-слово, у которого есть по крайней мере пара разных написаний, которые, я думаю, не разрешены на номерных знаках.

Другой пример - определение всех различных порядков слов с использованием заданного алфавита, который содержит некоторые элементы, повторяющиеся несколько раз. Например, если кто-то хочет, чтобы буквы в слове «буква» располагались разными способами, это не просто шесть! что могло бы быть в случае "abcdef", потому что есть 2 пары букв, которые немного усложняют вычисление.

L33t может быть еще одним способом усложнить идентификацию неподходящих слов, так как в то время как задница подвергается цензуре $$ или @ss не обязательно могут трактоваться одинаково, даже если это один и тот же термин, выраженный по-разному. Я'

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

Жесткая часть - это определение структуры данных таким образом, который может быть сгенерирован вашими правилами и может иметь операции над набором. Это! Это упражнение для читателя, ИНАЧЕ, у меня ничего нет.