Анализ алгоритма Средства поиска Перестановки (псевдо код)
ТАКИМ ОБРАЗОМ, сообщение о генерации всех перестановок получило меня думающий о нескольких альтернативных подходах. Я думал об использовании offs торговли пространства/времени выполнения и задавался вопросом, могли ли люди критиковать этот подход и возможные отклонения при попытке реализовать его в C#.
Шаги идут следующим образом:
Учитывая структуру данных гомогенных элементов, считайте число элементов в структуре.
Принятие перестановки состоит из всех элементов структуры, вычислите факториал значения от Шага 1.
Инстанцируйте более новой структуры (Словарь) типа
Хеш (???) структура семени от шага 1, и вставляет пару ключ/значение хеша и набора в Словарь. Увеличьте счетчик 1.
Случайным образом перестановка (???) порядок структуры семени, хешируйте его и затем попытайтесь вставить его в Словарь от шага 3.
Если существует конфликт в хешах, повторите шаг 5 снова для получения нового порядка и хеша и проверки на конфликт. На успешную вставку увеличивают счетчик 1.
Повторите шаги 5 и 6, пока счетчик не будет равняться факториалу, вычисленному на шаге 2.
Это походит на выполнение его этот способ использовать своего рода randomizer (который является черным квадратом мне в данный момент), мог бы помочь с получением всех перестановок в течение достойного периода времени для наборов данных непристойных размеров.
Будет замечательно заставить некоторую обратную связь от великих умов ТАК далее анализировать этот подход, цель которого состоит в том, чтобы отклониться от традиционного метода решения "в лоб", распространенного в алгоритмах такой природы и также последствий реализации такого алгоритма с помощью C#.
Спасибо
2 ответа
Этот метод генерации всех перестановок не очень хорош по сравнению со стандартными известными методами.
Допустим, у вас есть n предметов и M = n! перестановки.
Ожидается, что этот метод генерации сгенерирует перестановки M * lnM перед обнаружением всех M.
(Возможное объяснение см. В этом ответе: Программирование жемчужин - алгоритм случайного выбора )
Также, какой была бы хеш-функция? Для разумной хэш-функции нам, возможно, придется довольно скоро начать иметь дело с очень большими целочисленными проблемами (наверняка любое n> 50, не помните точную точку отсечения).
Этот метод также использует много памяти (хеш-таблица всех перестановок).
Даже если предположить, что хэш идеален, этот метод потребует ожидаемых операций Omega (n M logM) и гарантированного пространства Omega (nM), в то время как стандартные известные методы могут сделать это за O (M). время и O (n) пространство.
В качестве отправной точки я предлагаю прочитать: Систематическая генерация всех перестановок , которая считается O (нМ) временем и O (n) пространством и все же намного лучше, чем этот метод.
Обратите внимание, что если нужно сгенерировать все перестановки, любой алгоритм обязательно будет выполнять шаги Омега (M), и поэтому метод, о котором я говорю выше, является оптимальным!
Похоже на сложный способ рандомизировать порядок сгенерированных перестановок. С точки зрения экономии времени вы не можете добиться большего, чем метод «грубой силы».