Эффективное определение уникальных перестановок
У меня есть следующая проблема. Мне нужно вычислить перестановки множества; однако набор может содержать два элемента, которые являются одинаковыми и поэтому вызывают повторные перестановки. Например:
Учитывая набор [ 0 0 1 2 ]
, перестановки включают следующие возможности:
1 2 0 0
1 2 0 0
Однако я хотел бы избежать аналогичных перестановок, таких как эти. В MATLAB я могу просто сделать это:
unique(perms([ 0 0 1 2 ]), 'rows')
Но проблема здесь в эффективности - я делаю это многократно в огромном цикле for
, и сортировка, требуемая unique
, слишком медленная. Поэтому мой вопрос: могу ли я вычислить уникальные перестановки такого характера непосредственно, не зацикливая результат после этого? Я работаю в MATLAB, но просто общее решение, вероятно, будет полезно, хотя что-то, что может быть векторизовано в MATLAB, вероятно, будет идеальным!
Насколько я вижу, существующие вопросы не охватывают именно эту проблему, но приносят извинения, если это было ранее ответили.
Ответы
Ответ 1
Казалось бы, это регулярно возникающая проблема. Здесь - файл Джона д'Эрико (uniqueperms
), который, похоже, довольно эффективно справляется с этим. В качестве альтернативы есть еще одно сообщение FEX здесь от Ged Ridgway; вам придется немного профилировать, чтобы узнать, какой из них быстрее.
Обратите внимание, что из-за ограничений Matlab JIT циклы не ускоряются, если они вызывают нестрочные функции, поэтому было бы полезно скопировать вложенные данные этих функций (и/или их немного настроить) внутри вашего цикл (ы).