Анализ алгоритма поиска перестановок (псевдокод)

Question

A ТАК сообщение о генерации всех перестановок заставило меня задуматься о нескольких альтернативных подходах.Я думал об использовании компромиссов между пространством и временем выполнения и задавался вопросом, могут ли люди критиковать этот подход и возможные икоты, пытаясь реализовать его в C #.

Шаги выполняются следующим образом:

1. Учитывая структуру данных однородных элементов, подсчитайте количество элементов в структуре.

2. Предполагая, что перестановка состоит из всех элементов структуры, вычислитефакториал значения из шага 1.

3. Создание более новой структуры (словаря) типа <key(Somehashofcollection),Collection<data-structure of homogeneous elements>> и инициализация счетчика.

4. Хэш(???) начальную структуру из шага 1 и вставьте пару ключ / значение хеша и коллекции в словарь.Увеличьте счетчик на 1.

5. Произвольно перемешайте (???) порядок структуры семени, хешируйте его, а затем попытайтесь вставить его в словарь с шага 3.

6. Если в хешах есть конфликт, повторите шаг 5 еще раз, чтобы получить новый порядок и хэш и проверить конфликт.После успешной вставки увеличьте счетчик на 1.

7. Повторяйте шаги 5 и 6, пока счетчик не будет равен факториалу, вычисленному в шаге 2.

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

Было бы здорово получить отзывы от великих умов SO для дальнейшего анализа этого подхода, цель которого состоит в том, чтобы отклониться от традиционного подхода грубой силы, преобладающего в алгоритмах такого характера, а также от последствий реализации таких подходов.алгоритм с использованием C #.

Спасибо

Answer 1

Этот метод генерации всех перестановок не очень хорош по сравнению со стандартными известными методами.

Скажем, у вас было n предметов и M = n! Перестановки.

Ожидается, что этот метод генерации генерирует M * lnM перестановок, прежде чем обнаружит все M.

(См. Этот ответ для возможного объяснения: Программирование жемчужин - алгоритм случайного выбора )

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

Этот метод также использует много памяти (хеш-таблица всех перестановок).

Даже если предположить, что хеш идеален, этот метод будет принимать ожидаемые операции Омега (n M logM) и гарантированное пространство Омега (нМ), в то время как стандартные известные методы могут делать это в O (M) время и O (n) пространство.

В качестве отправной точки я предлагаю прочитать: Систематическое генерирование всех перестановок , которое, как полагают, является O (нМ) временем и O (n) пространством и все еще намного лучше, чем этот метод.

Обратите внимание, что если нужно сгенерировать все перестановки, любой алгоритм обязательно предпримет шаги Омега (М), и поэтому метод, на который я ссылаюсь выше, является оптимальным!

Answer 2

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