С огромным удовольствием смотрю Ваши видео, спасибо большое за Ваш труд, выпускайте пожалуйста видео почаще
@frontendscience3 жыл бұрын
Спасибо за поддержку! Очень вдохновляет. Как раз снимаю новое видео. 😀
@WebInterview3 жыл бұрын
Можно еще чуть сократить - использовать деструктурирующее присваивание, вроде [arr[i], arr[rnd]] = [arr[rnd], arr[i]]; Спасибо за контент :)
@frontendscience3 жыл бұрын
Да, сократить можно конечно. Использовал тут вариант с доп переменной, чтобы было наглядней.
@stravoytov Жыл бұрын
Отличное видео, спасибо большое за разъяснения. Много статей перечитал, но так и не понял логики. А тут всё логично объяснено.
@dmitrykorovin43563 жыл бұрын
спасибо за ваши видео, не канал, а находка!
@frontendscience3 жыл бұрын
И Вам спасибо за слова поддержки! Рад стараться)
@PEDRO-rs6ei Жыл бұрын
function shuffle(array) { for (let i = 0; i < array.length; i++) { let rand = Math.floor(Math.random() * array.length) let tmp = array[array.length - i - 1] array[array.length - i - 1] = array[rand] array[rand] = tmp } return array }
@ВиталийЗамирайло-щ9к3 жыл бұрын
Приятно, когда в начале видео написал своё решение, и этот вариант в последствии советует автор. Кстати, дополнительная переменная tmp не обязательна, можно просто [ arr[ rnd ], arr[ i ] ] = [ arr[i], arr[ rnd ] ];
@frontendscience3 жыл бұрын
Да 0 можно свайпнуть значения деструкутризацией - но так сложнее читать код и для обучающего видео всегда предпочитаю делать избыточные переменные - зато все понятно :) В продашен проектах вполне можно использовать деструктуризацию - если утвержденный кодстайл на проекте позволяет.
@DenProgMan3 жыл бұрын
Решил пройтись с начала и брать весь диапазон, а не только оставшийся от текущей позиции, т.е. мой алгоритм меняет местами по всему массиву, вроде понятно объяснил :-D function shuffle(array) { for (let index = 0; index < array.length; index++) { const element = array[index]; const randomIndex = Math.floor(Math.random() * array.length); array[index] = array[randomIndex]; array[randomIndex] = element; } return array; }
@DenProgMan3 жыл бұрын
Math.floor, кстати, можно заменить на двойную тильду: Math.floor(Math.random() * array.length); ~~(Math.random() * array.length);
@ЕгорЧилиевич-ю9р3 жыл бұрын
такое перемешивание выдает не равномерно распределенные перестановки
@EvilYou3 жыл бұрын
Задачу из видео решил быстро, так как уже встречал такую раньше, но зайдя на leetcode, увидел дополнительные условия, там она немного усложнена прототипами. Мое решение с использованием синтаксиса классов: class Solution { constructor(nums) { this.nums = nums; } reset() { // возвращает первоначальный массив return this.nums; } shuffle() { // сортирует (задача из видео) let arr = this.nums.concat(); for (let i = arr.length - 1; i > 0; i--) { let random = Math.floor((i + 1) * Math.random()); [arr[i], arr[random]] = [arr[random], arr[i]]; // (*) } return arr; } } * - использовал деструктурирующее присваивание для более короткой записи, а также потому, что не нужна дополнительная переменная для хранения промежуточного значения. Результат на leetcode: Runtime: 224 ms, faster than 91.86%
видео очень полезное , спасибо что так подробно разобрали задачу ❤
@ПетроПередерий-р1у2 жыл бұрын
Я обычно делаю так. В цикле беру 2 случайных элемента и меняю их местами (а не как у автора перебор массива от конца к началу). В чём разница? А в том что я задаю количество итераций в цикле как захочу. Если мне нужно перемешать как у автора то достаточно сделать количество итераций в цикле равным половине длины массива. Но если мне нужно перемешать массив только ЧУТЬ-ЧУТЬ то я задаю меньшее число итераций чем половина длины массива. Можно задать число итераций и больше чем половина длины массива для "более крутого" перемешивания. Но это не имеет практического смысла.
@vovaseagull10973 жыл бұрын
Спасибо большое за видео!) Я решил пойти через рекурсию и понервничал) вот решение: const arr1 = [1, 2, 4, 76, 55, 33] const shuffle = (array) => { const newArray = []; const addNewNumToArray = (num) => { if (newArray.length === array.length) { return newArray } if (newArray.includes(num)) { return addNewNumToArray(array[Math.floor(Math.random() * array.length)]) } newArray.push(num) return addNewNumToArray(array[Math.floor(Math.random() * array.length)]) } return addNewNumToArray(array[Math.floor(Math.random() * array.length)]); } console.log('shuffle exec', shuffle(arr1))
@frontendscience3 жыл бұрын
Сурово! :) тоже занервничал
@EvilYou Жыл бұрын
Кстати, кто хочет проверить правильность своей функции, это можно сделать так: function shuffle(arr) { // ваша функция shuffle (здесь привел свою) for (let i = arr.length - 1; i > 0; i--) { let random = Math.floor( Math.random() * (i + 1) ); [arr[random], arr[i]] = [arr[i], arr[random]]; } } let arr = [1, 2, 3]; let obj = { 123: 0, 132: 0, 213: 0, 231: 0, 312: 0, 321: 0, }; for (let i = 0; i < 1e5; i++) { shuffle(arr); obj[arr.join('')]++; } console.log(obj); // у меня все значения вышли от 16471 до 16768 распределение должно быть плюс минус одинаковым.
@Strangers-n8k3 ай бұрын
Знакомый код
@s.i.99883 жыл бұрын
Отлично! :)
@frontendscience3 жыл бұрын
👍
@Neravarinn3 жыл бұрын
Учу js и ничего умнее не придумал, чем решение в лоб. Спасибо за интересную задачку. let array = [1,2,3,4,5,6,7,8,9,10] let shuffle = function(arr) { let j=arr.length let count = new Array for (let i=1; i
@frontendscience3 жыл бұрын
Благодарю за решение
@valeriakan64742 жыл бұрын
Классная задачка, а вот мое супер неоптимальное решение, решила зачем-то сделать хэш, короче жуть, но вам в копилку комментов: let input = [10,20,30,40,50] const shuffleMy = (arr) => { const obj = {} let len = arr.length; arr.forEach((elem) => { // Set random order for each element in array, ex: obj = {'10': 5, '20': 1, '30': 3, '40': 4, '50': 2} let k = getRandomInt(len); if (Object.values(obj).indexOf(k) > -1){ do { k = getRandomInt(len); } while (Object.values(obj).indexOf(k) > -1) } obj[elem] = k }) return Object.entries(obj).sort((a, b) => a[1] - b[1]).map((elem) => elem[0]); } function getRandomInt(max) { return Math.floor(Math.random() * max); } for (let i = 0; i < 5; i++) { console.log(shuffleMy(input)) }
@frontendscience2 жыл бұрын
Благодарю за решение! Интнесный вариант вышел! 👍
@empfaze3 жыл бұрын
Добрый день! const input = [1, 2, 3, 4, 5]; const shuffle = function (arr) { const result = []; for (let i = 0; i < arr.length; i++) { let tmpIndex = Math.floor(Math.random() * arr.length); while (result[tmpIndex]) { tmpIndex = Math.floor(Math.random() * arr.length); } result[tmpIndex] = arr[i]; } return result; //return arr.sort((prev, next) => Math.random(next) - Math.random(prev)); }; console.log(shuffle(input));
@frontendscience3 жыл бұрын
Благодарю! Вышло клево!
@denisoleksyuk53463 жыл бұрын
перед началом видео попробовл свой вариант, и потом понял что опять затупил, сделал переменую для последнего индекса хотя можно было циклом же идти из конца ): ```js const shuffle = (arr) => { let lastIndex = arr.length - 1; for (let i = 0; i < arr.length; i++) { const rnd = Math.floor(Math.random() * lastIndex); [arr[rnd], arr[lastIndex]] = [arr[lastIndex], arr[rnd]] lastIndex-- } return arr };```
@frontendscience3 жыл бұрын
Благодарю за решение!
@lostsouls31513 жыл бұрын
Вот что получилось, тоже это прям простой вариант const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]; function shuffle(arr) { for (var i = 0; i < 10; i++) { arr.sort(() => 0.5 - Math.random()); console.log(arr); } } shuffle(numbers);
@frontendscience3 жыл бұрын
Благодарю за решение!
@Shtirlic_Isaev3 жыл бұрын
Интуитивно, мне ваше решение кажется более простым и понятным. Правда, так как это сортировка, то сложность этого лаконичного алгоритма будет уже O(N*log(N))
@frontendscience3 жыл бұрын
@@Shtirlic_Isaev Да помимо большей сложности есть еще момент с неравномерным распределением (скажем так не достаточно равномерной рандомности).
@Shtirlic_Isaev3 жыл бұрын
@@frontendscience Да, позже прочитал об этом в другой ветке комментариев... И этот эффект значительно интереснее, требует гораздо более глубокого понимания !
@St3rnhunt3r3 жыл бұрын
ЧтоЖ) Я сделал вот так: let input = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; function shuffel(rand) { rand.sort(() => Math.random() - 0.5); } shuffel(input); console.log(input);
@frontendscience3 жыл бұрын
:) Я это называю - "сортировка - загадочная"!
@ИмяФамилия-э4ф7в3 жыл бұрын
Чёт стрёмно. В документации есть требование, что колбек для одних и тех же элементов должен возвращать одинаковый результат. Иначе сортировка будет неустойчивой (это нас, в данном случае, не парит) и неопределённой по времени, да и вообще, наверное, может выдать ошибку. Самую лучшую из ошибок: которая иногда появляется (не воспроизводимую). Это отдельная мука в аду, фиксить такие ошибки.
Интересный алгоритм. Пару мыслей по поводу: - Мы же не обязаны проходить по всему массиву, мы можем пройти до половины, до трёх четвертей; пройти полтора, два или 42 раза по массиву. Интересно, после какого минимального числа итераций, грубо говоря "степень смешанности массива" уже не увеличивается (и как её вообще определить)? - Мы же не обязаны брать случайное число от 0 до i, мы можем брать до arr.length. Как это повлияет на перемешивание, и повлияет ли вообще? Оба вопроса, очевидно, больше к математикам, чем к программистам.
@EvilYou3 жыл бұрын
1) Если нужна правильная (равномерная) сортировка, то обязаны. Например, если сортируем 1/5 массива из 10 элементов, то как минимум 6 элементов останутся на своих местах. Если проходить до 1/2 или 3/4 то там все равно есть вероятность у оставшихся элементов быть не сдвинутыми. 2) Вопрос хороший. Я протестировал на большом количестве массивов, у меня в обоих случаях вышел одинаковый результат.
@sokoloff1143 жыл бұрын
2. задумался и решил проверить. Получилось, что для короткого массива [1,2,3] разница просто огромна: при прогоне до (i+1) всё хорошо, а вот при прогоне до length определенные комбинации выпадают в 2 раза чаще других. Пояснение по коду: взял [1,2,3], перед сортировкой сделал копию (Сергей, кстати, сортирует каждый раз результат предыдущей сортировки, а не исходный массив). 9000 тысяч раз сортирую массив и записываю получившийся результат (вариантов всего 6, поэтому все наглядно получилось). Соответственно, в среднем на 9000 прогонов и 6 вариантов каждая комбинация должна выпадать примерно 1500 раз. При i+1 так и вышло. const arr = [1,2,3]; function shuffle(array) { const shuffled = array.slice(); for (let i = shuffled.length - 1; i > 0; i--) { let j = Math.floor(Math.random() * (i+1)); // or shuffled.length [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]]; } return shuffled.join(''); } const results = [0,0,0,0,0,0]; for (let i = 0; i < 9000; i++) { const res = shuffle(arr); if (res === '123') results[0]++; if (res === '132') results[1]++; if (res === '312') results[2]++; if (res === '231') results[3]++; if (res === '321') results[4]++; if (res === '213') results[5]++; } console.log(results); // [ 2028, 1955, 1973, 1004, 1025, 1015 ] for length // [ 1520, 1513, 1530, 1439, 1511, 1487 ] for i+1
@alexanderruzhik92342 жыл бұрын
Вот мой вариант программы, написал его до просмотра решения и возник вопрос: Можно ли использовать вместо (i + 1) --- arr.length и обязательно ли совершать обход с конца массива?? function random(arr) { for (let i = 0; i < arr.length; i++) { const random = Math.floor(Math.random() * arr.length); [arr[i], arr[random]] = [arr[random], arr[i]]; } return arr; }
@frontendscience2 жыл бұрын
Да, прекрасный вариант. Разницы нету, что с начала, что с конца - эффект будет такой же.
@medvedovsky20282 жыл бұрын
Разница будет. Вероятность некоторых исходов больше, чем других (можно проверить циклом). Возможно это из-за того, что начиная сначала числа оставшиеся позади i также могут поменяться, в отличии от вариации с конца, где числа позади i не трогаются. let count = { '123': 0, '132': 0, '213': 0, '231': 0, '321': 0, '312': 0, toString() { return ` '123': ${count['123']}, '132': ${count['132']}, '213': ${count['213']}, '231': ${count['231']}, '321': ${count['321']}, '312': ${count['312']}, ` } } for (let i = 0; i < 1000000; i++) { let array = [1, 2, 3]; shuffle(array); count[array.join('')]++; }; console.log(String(count)) Итог: '123': 148536, '132': 184897, '213': 186002, '231': 184753, '321': 148272, '312': 147540," Такие дела
@jorgen54623 жыл бұрын
В субтитрах мне пишет: "с вами Сергей Пузырьков..." Ну, думаю, юморист, Серёга. Но нет, это ИИ юморит😂 хотя сортировки пузырьком тут, скорее всего, не будет 🤔
@frontendscience3 жыл бұрын
Смешная шутка! 😂
@wisarty2 жыл бұрын
Дякую
@artemDutchak3 жыл бұрын
Если мы поменяли местами последний элемент с третьим, получается, когда мы дойдем то третьего элемента, то его можно уже не менять, т.к. здесь "рандомно" уже другое значение, которое отличается от входящего массива. Я правильно понимаю?
@frontendscience3 жыл бұрын
ну может и так - но если ты его еще раз переставишь то так можно добиться более "высокого уровня" перемешиваемости
@artemDutchak3 жыл бұрын
@@frontendscience А я прям задумался... если функцию, основанную на Math.random(), вызвать дважды... будет ли результат более рандомный? Ведь эта функция не выдает абсолютно рандомное число, а вычисляет его как-то, и будет ли второй результат "более рандомный" чем первый? Как вообще можно измерить рандомность результата... И как можно написать свою функцию, выдающую рандомное число, кроме как с привязкой ко времени. Есть над чем подумать вместо сна :)
@yarik83men513 жыл бұрын
Java: public class ShuffleSortArray { public static void main(String[] args) { int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; for (int i = 0; i < 10; i++) { shuffleArray(array); } } private static void shuffleArray(int[] arr){ for (int i = 0; i < arr.length; i++) { int i1 = (int) (Math.random() * arr.length); int i2 = (int) (Math.random() * arr.length); int temp = arr[i1]; arr[i1] = arr[i2]; arr[i2] = temp; } System.out.println(Arrays.toString(arr)); } }
@rakhimovkamran3 жыл бұрын
array.sort((a, b) => Math.random() > 0.5 ? 1 : -1)
@Лесорубовлеха2 жыл бұрын
у меня блин не получилось. я даже не догадался как сделать через метод sort, но теперь понял как делать через фишера
@FredUA3 жыл бұрын
Не понял зачем умножать на i+1 (let rnd = Math.floor(Math.random() * (i + 1))). Получается, что чем ближе к нулевому элементу тем меньше шансов стать этому элементу в конец массива?
@frontendscience3 жыл бұрын
Нет. Распределение равномерное. Вот тут можно подробней почитать про рандомное целое число в определенном диапазоне. developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random#getting_a_random_integer_between_two_values У нас минимум -0, а максимум это i. При этом нам надо i включительно. Поэтому умножаем на i+1
@bibblebabl3 жыл бұрын
@@frontendscience А в чем преимущество идти с конца массива, а не с начала? от 0 до array.length? В чем профит?
@frontendscience3 жыл бұрын
@@bibblebabl ни в чем ) Можно инвертировать все и идти с начала массива - эффект будет тот же. Почему везде в книгах этот алгоритм приводится именно с началом в конце - не знаю. Видать так исторически сложилось.
@arealitcy3 жыл бұрын
@@frontendscience исторически сложилось из-за того, что бытует мнение, будто обход массива из конца в начало быстрее а если касательно именно этого алгоритма: могу предположить, что проходя массив в обратном порядке, на каждой итерации нужно выбирать случайное число в диапазоне [0, i], а не [i, arr.length], что выглядит чуть лаконичнее и требует меньше операций (но тоже такая себе оптимизация)
@andrey-frontend2 жыл бұрын
Я сначала думал из массива брать подряд числа и в зависимости от того что покажет рандом либо добавлять их в начало, либо добавлять в конец массива
@ВасилийБарков-к2э Жыл бұрын
Еще вариантик решения. Можно на листочке написать числа, положить их в шляпку и бабка какая-нибудь пусть вытягивает и называет номерки.
@inna1305 Жыл бұрын
почему бабка то
@ВасилийБарков-к2э8 ай бұрын
@@inna1305чтобы пенсионерка не скучала
@АлександрОхременко-н8й3 жыл бұрын
А как же функциональное программирование с его иммутабельностью?) Изначальный массив изменяется внутри функции, что не есть хорошо.
@frontendscience3 жыл бұрын
Для чего не хорошо? Для массива с огроменным объемом данных? Это задачи совсем не про иммутабельность - цена которой память и скорость.
@АлександрОхременко-н8й3 жыл бұрын
@@frontendscience давно фронтендеры занимаются обработкой огроменных массивов данных?) Любые мутации в процессе работы программы , потенциально, вызывают лишь геморрой, с которым после вас будет кто-то бороться и искать его, ценой в пару Кб оперативной памяти (не говорим о системах, которые обрабатывают огромные массивы данных, где пренебрежение этим вполне обоснованно, канал про фронтенд).
@frontendscience3 жыл бұрын
@@АлександрОхременко-н8й Фронтенд бывает разный) Он не только такой, как в Ваших фантазиях. Если Вы для себя определили уже Вашу зону компетенции и зону развития - не учите алгоритмы. Выбор всегда за Вами.
@frontendscience3 жыл бұрын
@@bohdanHutorIT Именно! Надо учитывать контекст! Конкретно в этом случае мы решаем задачи с Leetcode (попутно изучаем различные алгоритмы). На Leetcode для всех задач необходимо найти наиболее оптимальное решение как по времени, так и по памяти.
@-anonim-30082 жыл бұрын
Не понимаю, зачем нам нужно умножать на i+1 рандомное число
@andrey-frontend2 жыл бұрын
Функция рандом выводит рандомное число оно выглядит так 0
@Никита-ы1к2ш3 жыл бұрын
методом map возможно решить ?
@frontendscience3 жыл бұрын
Нет - через map не выйдет. С помощью map можно заполнить массив рандомными числами например, но перемешать имеющиеся элементы - не выйдет.
@michaelmorrison63793 жыл бұрын
мда уж, если бы на собесах такие задачи были :(
@frontendscience3 жыл бұрын
В смысле? :) Так они и бывают на собесах - поэтому мы эту рубрику и ведем) Мне лично в 2015 году на собеседовании дали эту задачу. Присылайте задачи, которые попадались Вам.
@VYuhim3 жыл бұрын
Лучше бы исходный массив не мутировать =)
@frontendrules73 жыл бұрын
Лучше, но тогда сложность по памяти будет O(n) а не O(1) ;)
@ИмяФамилия-э4ф7в3 жыл бұрын
Ну такое, если задача ставиться отсортировать массив, то он сортируется на месте, это довольно логично. То же самое и с перемешиванием, довольно ожидаемое поведение. Другое дело, что это должно быть оговоренно в требованиях изначально.
@frontendscience3 жыл бұрын
@@ИмяФамилия-э4ф7в На Leetcode во всех задачах необходимо найти решение наиболее оптимальное как по времени, так и по памяти.
@ИмяФамилия-э4ф7в3 жыл бұрын
@@frontendscience это тут ни при чём. Требование мутировать или не мутировать входные данные внешнее по отношению к задаче. Т.е. в условии должно быть либо "вернуть новый массив, который ..." либо "перемешать данный массив..." А вот как реализовать указанное поведение оптимально по времени и по памяти - это вопрос задачи.
@frontendscience3 жыл бұрын
@@ИмяФамилия-э4ф7в Для того чтобы не мутировать входные данные, их необходимо будет скопировать. И это значит, что уже по памяти сложность будет O(n), а не O(1). Причем тут Ваш комментарий? У задачи есть четкие требования.
@viv81ster3 жыл бұрын
Если точно знать что значения только int то можно избавится от tmp переменной
@frontendscience3 жыл бұрын
Даже если можно избавиться - ч в решениях часто делаю избыточные переменные в угоду читаемости и для лучшего понимания что происходит в коде. К счастью на результирующую сложность это не особо влияет.
@ПетроПередерий-р1у3 жыл бұрын
Ну, блин, что за выражение ОТСОРТИРОВАНО в случайном порядке???? Да не отсортировано, а ПЕРЕМЕШАНО случайным образом. Я уже с перепугу подумал что можно сортировать массивы в убывающем или возрастающем порядке с помощью рандома.
@frontendscience3 жыл бұрын
Ну вообще то есть такое выражение отсортирован в случайном порядке. Это и есть принцип сортировки - случайный порядок. Кстати когда-то видел вариант когда в функции sort, рандомным образом выбиралось -1,0,1 :)
@ИмяФамилия-э4ф7в3 жыл бұрын
Можно сортировать, не вижу проблем. Перемешиваешь, проверяешь: если для каждого i arr[i] >= arr[i+1] то возвращаем результат, если нет, то снова перемешиваем... По-моему, этот алгоритм лежит в основе работы Windows, visual studio, android studio и т.п. Но это не точно...
@arealitcy3 жыл бұрын
вообще можно, алгоритм называется bogosort (эзотерический алгоритм, больше для фана, чем для реальной пользы)
@ruff3d3 жыл бұрын
не глядя решение [1,2,3,4,5].sort(()=>Math.floor(Math.random()*10) % 2 || -1)
@hakobandreasyan82393 жыл бұрын
а почему атор не упомянул эту версию ? const shuffle = (arr) => arr.sort(() => 0.5 - Math.random());
@andreylomakin63533 жыл бұрын
@@hakobandreasyan8239 потому что мы мутируем arr, нужно [...arr]
@goldstein13 жыл бұрын
Оно должно получиться больше по сложности, тк алгоритм сортировки внутри js в таком случае делает больше итераций) В документации напрямую просят не использовать конструкцию, возвращающую неопределенный результат, тк, кроме неустойчивого времени выполнения, могут быть выброшены неожиданные исключения
@ruff3d3 жыл бұрын
@@andreylomakin6353 оно ж просто возвращает, не мутирует....🤔