How to become an author
Search
Write a publication
Pull to refresh

Comments 31

Подход, конечно, интересный. Но вы как-то неожиданно алгоритмическую сложность получения всего ряда длинной (n!) подменили сложностью вычисления следующего значения. Более того, вместо линейной (или в случае с деревом log(n)) сложности получения следующего значения добавили сравнительную (компаративную) сортировку суффикса, которую надо оценивать как O(n*log(n)). Так что, если оценивать алгоритмическую сложность генерации всего ряда, у вас получится, если я не ошибаюсь O(n!*n*log(n)) как-то так
Total votes 3: ↑3 and ↓0+3
Помойму сложность n*log (n)
Total votes 1: ↑1 and ↓0+1
Сложность алгоритма на выходе которого n! элементов точно не может быть ниже чем O(n!). Согласен, что O(n!) * O(n* log(n)) это завышенная оценка. Надо более внимательно считать, что да как.
Также, в рамках этой задачи видно, что в исходном множестве элементы могут повторяться (в примере повторяется 0). Соответственно, тождественные строки, вызванные перестановкой одинаковых элементов, не должны повторяться на выходе. Потому на выходе алгоритма может быть меньше чем n! элементов.
Total votes 2: ↑2 and ↓0+2
Да вы правы, я неправильно прочитал и оценивал сложность написанного алгоритма, а не проблемы в целом.
Total votes 2: ↑2 and ↓0+2

Разве тут перемножением сложностей. Вы находите суффикс за n и потом делаете сортировку. Получается n + log(n)

This comment wasn’t rated yet0
В вашем коде n*log(n), а можно действительно за линейную сложность, по сути sort суффикса новый это revers его, получает n на поиск суффикса, потом binary search на элемент который надо поменять(log (n)) и reverse (n/2) получается O(n)
Total votes 1: ↑1 and ↓0+1

Это хорошая идея. Спасибо.

This comment wasn’t rated yet0
Вы перепутали просто все. Сложность получения всех возможных перестановок и сложность получения следующей перестановки это совсем разные вещи.

Можно бороться только за уменьшение сложности получения следующей перестановки. Гуглить по словам DFS и DP. Все делается гораздо и быстрее проще чем у вас.
Total votes 1: ↑1 and ↓0+1

DFS это поиск в графу, я что-то не совсем понимаю, как он может подойти в данном случае.

This comment wasn’t rated yet0
Так называют любой алгоритм работающий в глубину.
Граф или дерево это просто самый простой пример.
This comment wasn’t rated yet0

Я посмотрю, но мне кажется это не совсем тот случай.

This comment wasn’t rated yet0
Тот.
дано 1234
результаты
1
21 12
321 231 213
4321 3421 3241 3214

Типичный же случай.
This comment wasn’t rated yet0

По большому счету это алгоритм перестановок. Мне кажется в этом контексте он бесполезный. Да, я могу построить граф, что замете n! времени, а потом поиском по графу найти найти нужную перестановку, что ещё займёт О (m + n). Я не говорю, что его нельзя использовать, просто это не эффективно.

This comment wasn’t rated yet0
Перечитал еще. Извиняюсь перепутал. Решил что вы все перестановки ищите.
Если надо именно минимальную чтобы было больше, то у вас все как надо.
Total votes 1: ↑1 and ↓0+1
Что касается практического применения алгоритма, то за все время моей работы он мне ни разу не понадобился, но на интервью в Uber посчитали иначе :))

В Убер-то взяли? Вы забыли добавить в конце статьи:
Заголовок спойлера
image

Total votes 1: ↑1 and ↓0+1

Нет :)) Не прошёл парное программирование — тяжело одновременно думать, писать код и при этом ещё и пояснять на английском ход мыслей:)). Сам виноват, нужно разбираться в задаче, даже если тебя интервьюеры пинают сразу писать код..

This comment wasn’t rated yet0

Все так или иначе уже известно. Не нашёл на хабре пояснения и решил добавить.

Total votes 1: ↑1 and ↓0+1

А чтобы вы хотели? Чтобы я пошёл статью на английском, перевёл ее и получил свой рейтинг.

This comment wasn’t rated yet0
Я вообще не вижу смысла в отдельной статье для этого алгоритма. Всему этому место где-нибудь на тостере.
Total votes 2: ↑1 and ↓10

Обсуждение статьи не будет полным без ссылки на std::next_permutation. Хотя лично я никогда не понимал, что эта функция вообще делает в стандартной библиотеке С++.

Total votes 1: ↑1 and ↓0+1
Я не глубокий знаток C++. В других языках не встречал.
This comment wasn’t rated yet0

Но кажется довольно удобно
Можно решить данную задачу в C++ несколькими строчками (так как next_permutation изменяет строку, нужно еще ее вернуть, поэтому несколько)

This comment wasn’t rated yet0
тут линейная сложность (2 прохода по массиву), сортировка тут не нужна, т.к. суффикс уже отсортирован, его нужно просто развернуть
проверить алгоритм можно тут leetcode.com/problems/next-permutation
за решение спасибо, я его не знал
Total votes 1: ↑1 and ↓0+1
Да, тут уже упомянуло об этом. Идея здравая. Спасибо.
This comment wasn’t rated yet0
Uber, кстати, не парится совсем на тему задачек и спокойно берет их из сети. Не так давно (полгода назад примерно) был у них выложен тест на hackerrank.com в разделе работа. Дак вот, было там 3 задачи прямо из первой десятки сайта leetcode.com :/

сперли они значит эти задачи (назывался тест что-то типа Задачи от Алисы), а тестовый код не смогли — на С# закоммитил (естественно, свои решения с leetcode), тесты упали с ошибкой компиляции тестового окружения :) не ожидал такого от Uber
This comment wasn’t rated yet0
Откровенно говоря меня тут даже пугают не столько задачи, которые, как вы сказали, берут их без зазрения совести на hackerrank или leetcode. Часто интервью состоит из всяких разговорных интервью, берут скажем ланч и ты сидишь с незнакомым человек, с вилкой в руках и вы пытаетесь общаться обо всем. А потом приходит второй такой же чувак и вы опять общаетесь, только теперь на какие-то отвлеченные темы. Вот пример — пришел чувак и начал меня спрашивать, как построен поиск музыки в Shazam — я предположил, что они бьют музыку на части, делают хеши пиков и потом производят поиск, но я ошибся в том, что они на основании хешей строят кривые Безье и по сути сравнивают кривые. Мы долго спорили, в результате он сказал, что он ожидал от меня ответа, что они используют поиск в глубину по графу. Я пришел домой, проверил и мое предположение было верным.
Потом пришел менеджер и расспрашивал меня, как бы я улучшил их приложение. Это был не Uber, на что я высказал несколько идей, он сказал, что они это уже реализовали. К чему это было — для меня не совсем понятно.
This comment wasn’t rated yet0

В книге Д. Кнута "Искусство программирования. Том 4, выпуск 2. Генерация всех кортежей и перестановок" обсуждается также алгоритм P, в котором все перестановки перебираются путём замены пары смежных элементов на каждом шаге. Я когда-то давно нашёл алгоритм для этого с пом. подсчёта числа беспорядков, но алгоритм P работает быстрее, тем более он быстрее, чем лексикографический метод. Он использует два вспомогательных массива такого же размера, как и массив с перестановкой, а я обошёлся без доп. массивов. В книге Окулова "Программирование в алгоритмах" также есть алгоритм P.

Недавно я нашёл алгоритм получения перестановки по её номеру в соответствии с алгоритмом P, такого алгоритма я нигде пока не видел. Написать, что ли, статейку об этом? Скажут: маловато материала...

Также у Кнута поставлена задача генерации перестановок быстрейшим путём на совр. процессорах, эта задача остаётся открытой.

Total votes 2: ↑2 and ↓0+2

Спасибо, я не знал - попробую почитать за "алгоритм P".

This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr