3 алгоритма перестановок (рекурсия и итерация)

[@TrevoZnaniy]

с конца обрабатывать элементы как-то по-арабски, не привычно. Вот с лева на право вариант: function perm(arr, n = 0) { if (n == arr.length - 1) { console.log(arr); } for (let i = n; i < arr.length; i++) { [arr[i], arr[n]] = [arr[n], arr[i]]; perm(arr, n + 1); [arr[i], arr[n]] = [arr[n], arr[i]]; } } perm(['0', '1', '2'])

[@СергейАрхангельский-н2л]

Ага. Офигенски. Только вот ваш кот не делает нифига никаких перестановок

[@Рома-с5д]

@@СергейАрхангельский-н2л все переворачивает

[@VERTinBY]

при большом подмножестве элементов , алгоритму желательно уметь продолжить с места остановки , Комбинаторика она такая...

[@albrehtdurer557]

ну конечно, спасибо кэп)), если память кончилась?

[@VERTinBY]

@@albrehtdurer557 когда ищешь заветную комбинацию уже не первый месяц - есть посерьезнее страхи :)

[@IvanGavr]

Алгоритм Нараяны такое может. По этой причине можно и распараллелить его явно. На разных терминалах задать начало и остановку (от сих и до сих). Вот только не могу понять одного, почему некоторые считают, что рекурсивные алгоитмы легче для понимания.

[@TwilightSun32]

В первом варианте наверное можно уточнить, что элементы массива подразумеваются различные, иначе будет работать странно. Остальные два работают как-то логично в этом случае. Ещё помню в детстве делал нумерацию перестановок, т.е. функцию которая возвращает перестановку по номеру. не помню для какой задачи нужно было ... но чтобы придумать как это сделать - пришлось подумать, это хорошо помню. идею "каунтдаун" отдельно делал в какой-то задачке на кодварсе для замены рекурсии. т.е. по сути эту идею можно ещё пояснить так: рекурсивные вызовы в цикле это по сути n вложенных циклов, а их можно заменить на один цикл по составному счетчику (т.е. массиву счетчиков) который дополнительно небольшим циклом ещё согласованно инкрементируется или декрементируется (по сути это как работа с числом поразрядно, ещё на это похоже). Это я к тому что все эти идеи они могут быть отдельно в разных комбинациях встречаться в других алгоритмах каких-то.

[@АрсенАбдигали-м1м]

одно из самых полезных роликов по базовым алгоритмам на Ютубе, спасибо вам! хотелось бы узнать как вы изучали их, какие книги читали

[@S0ERDEVS]

Мне нравится Кормен, не сильно сложно, как у Кнута и не так поверхностно как у Скиены или Грокаем алгоритмы. Но читать я рекомендую все книги, они все таки немного разные и дают разные взгляды на алгоритмы. Какие-то вещи сначала "потрогать" в простом и слегка поверхностном варианте. а потом уже на этом понимании копнуть глубже.

[@alekseytrump1586]

Русский Том Харди. Ганстер среди программистов)))

[@joker202]

Русский Линус Торвальдс))

[@mrkotyuk]

@@joker202 кста чем-то внешностью похожи

[@alicenNorwood]

мистер вульф

[@arisman20]

не читал все комментарии, поэтому извините, если дубль... "Легкое" объяснение смены, как мне кажется заключается в том, что если массив можно разделить на 2 равных подмассива, то замена будет заключаться в циклической (хочется написать рекурсивном) замене не элементов, а именно этих подмассивов, если же на каком то шаге заменить нельзя - то находится элемент поссеридине, который сам на себя не меняется, и меняются местами 2 подмассива - один слева, другой справа .... В письменном изложении, возможно не так понятно, если это все проговорить - то, как мне кажетсься, очень легко ...

[@atom-kor]

Не хочу говорить громких слов, но ваше объяснение внесло ещё больше ясности в мою соломенную голову! 😅

[@shickulaairships]

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

[@ostrov11]

Спасибо.

[@kookaburru]

А можно переставлять элементы по порядку пока не закончатся варианты и реализуется это простым вложенным циклом for :)

[@shamilshiakhmetov6028]

некоторые задачи с for просто нельзя сделать без рекурсии. Та же NP-полная задача про ферзей

[@ivanmatew568]

Думаю, что многим новичкам было бы интересно, как последний алгоритм переписать с использованием классов. Так, как бы он мог попасть в прод. Причем, не сразу конечный вариант, а все этапы рефакторинга.

[@ilyapro2815]

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

[@Сергей-у6и7б]

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

[@alexandervolkov97]

И вроде всё понятно, но мозг будто отказывается вникать) Видимо нужно больше времени уделять этому

[@poetry4538]

Последний алгоритм (итеративный) генерирует не в лексикографическом порядке?

[@keyjackei9581]

Спасибо за столь полезную информацию! Алгоритм с итеративным подходом крайне интересен. Не подскажете откуда алгоритм взяли? Хотелось бы побольше вникнуть

[@alexandervolkov97]

Он сам придумал, очевидно.

[@traxooza]

js one love :3

[@runrunning4359]

Для меня как для новичка ничего не понятно, так как в первом примере вы используете стрелочные функции😥

[@plur_ndbn]

Не переживай, для не новичков он тоже несёт околесицу вместо простого объяснения

[@alexandersmirnov4274]

а кто автор итеративного алгоритма?

[@horhegarsia4221]

Вызывать функцию, всё же, проще так: let lst = [0, 1, 2]; perm(lst, lst.length); Если я не прав - поправьте меня.

[@Сергей-у6и7б]

Разницы нет

[@horhegarsia4221]

@@Сергей-у6и7б Логически - да, визуально (по степени восприятия кода другим человеком) - огромная.

[@fusted4630]

еще проще в самой функции сделать perm(arr, n = arr.length) тогда у потребителя не будет никакой необходимости вникать в суть работы алгоритма

[@loh_ya]

у меня одного первый код вообще не работает?

[@TwilightSun32]

по поводу %2 проверил, если убрать - для случая из трех элементов перестановки начинают повторяться. т.е. дело в том, что нам в позицию i надо поставить элемент которого ещё не было, и для случая когда у нас слева от i четное количество позиций - такой элемент взять можно из начала, а когда нечетное - то он то в конце то перед ним, то ещё на 1 раньше и т.п. а почему оно так - это прям сложно сообразить сходу. это может быть даже проще по индукции будет доказать чем объяснить почему...

[@petr717.]

Автор вы делаете программу на заказ?

[@alexfomin2703]

Хочется написать j = i&1 ? p[i] : 0

[@TwilightSun32]

вот за эти сишные приколы жабаскрипт и не любят : )) (хотя для задач-однострочников на кодварсе полезно конечно)

[@СтасСеров-я7щ]

На каком языке примеры?

[@keyjackei9581]

По моему JavaScript

[@chinyass]

дед не души