Приятно, когда в начале видео написал своё решение, и этот вариант в последствии советует автор. Кстати, дополнительная переменная tmp не обязательна, можно просто [ arr[ rnd ], arr[ i ] ] = [ arr[i], arr[ rnd ] ];
Да 0 можно свайпнуть значения деструкутризацией - но так сложнее читать код и для обучающего видео всегда предпочитаю делать избыточные переменные - зато все понятно :) В продашен проектах вполне можно использовать деструктуризацию - если утвержденный кодстайл на проекте позволяет.
Решил пройтись с начала и брать весь диапазон, а не только оставшийся от текущей позиции, т.е. мой алгоритм меняет местами по всему массиву, вроде понятно объяснил :-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; }
Задачу из видео решил быстро, так как уже встречал такую раньше, но зайдя на leetcode, увидел дополнительные условия, там она немного усложнена прототипами. Мое решение с использованием синтаксиса классов: class Solution { constructor(nums) { this.nums = 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%
Я обычно делаю так. В цикле беру 2 случайных элемента и меняю их местами (а не как у автора перебор массива от конца к началу). В чём разница? А в том что я задаю количество итераций в цикле как захочу. Если мне нужно перемешать как у автора то достаточно сделать количество итераций в цикле равным половине длины массива. Но если мне нужно перемешать массив только ЧУТЬ-ЧУТЬ то я задаю меньшее число итераций чем половина длины массива. Можно задать число итераций и больше чем половина длины массива для "более крутого" перемешивания. Но это не имеет практического смысла.
Кстати, кто хочет проверить правильность своей функции, это можно сделать так: 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 распределение должно быть плюс минус одинаковым.
Вот что получилось, тоже это прям простой вариант 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);
Интуитивно, мне ваше решение кажется более простым и понятным. Правда, так как это сортировка, то сложность этого лаконичного алгоритма будет уже O(N*log(N))
@@frontendscience Да, позже прочитал об этом в другой ветке комментариев... И этот эффект значительно интереснее, требует гораздо более глубокого понимания !
Классная задачка, а вот мое супер неоптимальное решение, решила зачем-то сделать хэш, короче жуть, но вам в копилку комментов: 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)) }
перед началом видео попробовл свой вариант, и потом понял что опять затупил, сделал переменую для последнего индекса хотя можно было циклом же идти из конца ): ```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 };```
Вот мой вариант программы, написал его до просмотра решения и возник вопрос: Можно ли использовать вместо (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; }
Разница будет. Вероятность некоторых исходов больше, чем других (можно проверить циклом). Возможно это из-за того, что начиная сначала числа оставшиеся позади 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," Такие дела
Чёт стрёмно. В документации есть требование, что колбек для одних и тех же элементов должен возвращать одинаковый результат. Иначе сортировка будет неустойчивой (это нас, в данном случае, не парит) и неопределённой по времени, да и вообще, наверное, может выдать ошибку. Самую лучшую из ошибок: которая иногда появляется (не воспроизводимую). Это отдельная мука в аду, фиксить такие ошибки.
Если мы поменяли местами последний элемент с третьим, получается, когда мы дойдем то третьего элемента, то его можно уже не менять, т.к. здесь "рандомно" уже другое значение, которое отличается от входящего массива. Я правильно понимаю?
@@frontendscience А я прям задумался... если функцию, основанную на Math.random(), вызвать дважды... будет ли результат более рандомный? Ведь эта функция не выдает абсолютно рандомное число, а вычисляет его как-то, и будет ли второй результат "более рандомный" чем первый? Как вообще можно измерить рандомность результата... И как можно написать свою функцию, выдающую рандомное число, кроме как с привязкой ко времени. Есть над чем подумать вместо сна :)
Не понял зачем умножать на i+1 (let rnd = Math.floor(Math.random() * (i + 1))). Получается, что чем ближе к нулевому элементу тем меньше шансов стать этому элементу в конец массива?
Нет. Распределение равномерное. Вот тут можно подробней почитать про рандомное целое число в определенном диапазоне. 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
@@bibblebabl ни в чем ) Можно инвертировать все и идти с начала массива - эффект будет тот же. Почему везде в книгах этот алгоритм приводится именно с началом в конце - не знаю. Видать так исторически сложилось.
@@frontendscience исторически сложилось из-за того, что бытует мнение, будто обход массива из конца в начало быстрее а если касательно именно этого алгоритма: могу предположить, что проходя массив в обратном порядке, на каждой итерации нужно выбирать случайное число в диапазоне [0, i], а не [i, arr.length], что выглядит чуть лаконичнее и требует меньше операций (но тоже такая себе оптимизация)
Учу 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
Интересный алгоритм. Пару мыслей по поводу: - Мы же не обязаны проходить по всему массиву, мы можем пройти до половины, до трёх четвертей; пройти полтора, два или 42 раза по массиву. Интересно, после какого минимального числа итераций, грубо говоря "степень смешанности массива" уже не увеличивается (и как её вообще определить)? - Мы же не обязаны брать случайное число от 0 до i, мы можем брать до arr.length. Как это повлияет на перемешивание, и повлияет ли вообще? Оба вопроса, очевидно, больше к математикам, чем к программистам.
1) Если нужна правильная (равномерная) сортировка, то обязаны. Например, если сортируем 1/5 массива из 10 элементов, то как минимум 6 элементов останутся на своих местах. Если проходить до 1/2 или 3/4 то там все равно есть вероятность у оставшихся элементов быть не сдвинутыми. 2) Вопрос хороший. Я протестировал на большом количестве массивов, у меня в обоих случаях вышел одинаковый результат.
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]++; }
@@frontendscience давно фронтендеры занимаются обработкой огроменных массивов данных?) Любые мутации в процессе работы программы , потенциально, вызывают лишь геморрой, с которым после вас будет кто-то бороться и искать его, ценой в пару Кб оперативной памяти (не говорим о системах, которые обрабатывают огромные массивы данных, где пренебрежение этим вполне обоснованно, канал про фронтенд).
@@АлександрОхременко-н8й Фронтенд бывает разный) Он не только такой, как в Ваших фантазиях. Если Вы для себя определили уже Вашу зону компетенции и зону развития - не учите алгоритмы. Выбор всегда за Вами.
@@bohdanHutorIT Именно! Надо учитывать контекст! Конкретно в этом случае мы решаем задачи с Leetcode (попутно изучаем различные алгоритмы). На Leetcode для всех задач необходимо найти наиболее оптимальное решение как по времени, так и по памяти.
В субтитрах мне пишет: "с вами Сергей Пузырьков..." Ну, думаю, юморист, Серёга. Но нет, это ИИ юморит😂 хотя сортировки пузырьком тут, скорее всего, не будет 🤔
В смысле? :) Так они и бывают на собесах - поэтому мы эту рубрику и ведем) Мне лично в 2015 году на собеседовании дали эту задачу. Присылайте задачи, которые попадались Вам.
Ну такое, если задача ставиться отсортировать массив, то он сортируется на месте, это довольно логично. То же самое и с перемешиванием, довольно ожидаемое поведение. Другое дело, что это должно быть оговоренно в требованиях изначально.
@@frontendscience это тут ни при чём. Требование мутировать или не мутировать входные данные внешнее по отношению к задаче. Т.е. в условии должно быть либо "вернуть новый массив, который ..." либо "перемешать данный массив..." А вот как реализовать указанное поведение оптимально по времени и по памяти - это вопрос задачи.
@@ИмяФамилия-э4ф7в Для того чтобы не мутировать входные данные, их необходимо будет скопировать. И это значит, что уже по памяти сложность будет O(n), а не O(1). Причем тут Ваш комментарий? У задачи есть четкие требования.
Даже если можно избавиться - ч в решениях часто делаю избыточные переменные в угоду читаемости и для лучшего понимания что происходит в коде. К счастью на результирующую сложность это не особо влияет.
Ну, блин, что за выражение ОТСОРТИРОВАНО в случайном порядке???? Да не отсортировано, а ПЕРЕМЕШАНО случайным образом. Я уже с перепугу подумал что можно сортировать массивы в убывающем или возрастающем порядке с помощью рандома.
Ну вообще то есть такое выражение отсортирован в случайном порядке. Это и есть принцип сортировки - случайный порядок. Кстати когда-то видел вариант когда в функции sort, рандомным образом выбиралось -1,0,1 :)
Можно сортировать, не вижу проблем. Перемешиваешь, проверяешь: если для каждого i arr[i] >= arr[i+1] то возвращаем результат, если нет, то снова перемешиваем... По-моему, этот алгоритм лежит в основе работы Windows, visual studio, android studio и т.п. Но это не точно...
Оно должно получиться больше по сложности, тк алгоритм сортировки внутри js в таком случае делает больше итераций) В документации напрямую просят не использовать конструкцию, возвращающую неопределенный результат, тк, кроме неустойчивого времени выполнения, могут быть выброшены неожиданные исключения
С огромным удовольствием смотрю Ваши видео, спасибо большое за Ваш труд, выпускайте пожалуйста видео почаще
Спасибо за поддержку! Очень вдохновляет. Как раз снимаю новое видео. 😀
Отличное видео, спасибо большое за разъяснения. Много статей перечитал, но так и не понял логики. А тут всё логично объяснено.
спасибо за ваши видео, не канал, а находка!
И Вам спасибо за слова поддержки! Рад стараться)
Можно еще чуть сократить - использовать деструктурирующее присваивание, вроде [arr[i], arr[rnd]] = [arr[rnd], arr[i]];
Спасибо за контент :)
Да, сократить можно конечно. Использовал тут вариант с доп переменной, чтобы было наглядней.
Приятно, когда в начале видео написал своё решение, и этот вариант в последствии советует автор.
Кстати, дополнительная переменная tmp не обязательна, можно просто
[ arr[ rnd ], arr[ i ] ] = [ arr[i], arr[ rnd ] ];
Да 0 можно свайпнуть значения деструкутризацией - но так сложнее читать код и для обучающего видео всегда предпочитаю делать избыточные переменные - зато все понятно :) В продашен проектах вполне можно использовать деструктуризацию - если утвержденный кодстайл на проекте позволяет.
Решил пройтись с начала и брать весь диапазон, а не только оставшийся от текущей позиции, т.е. мой алгоритм меняет местами по всему массиву, вроде понятно объяснил :-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;
}
Math.floor, кстати, можно заменить на двойную тильду:
Math.floor(Math.random() * array.length);
~~(Math.random() * array.length);
такое перемешивание выдает не равномерно распределенные перестановки
видео очень полезное , спасибо что так подробно разобрали задачу ❤
Задачу из видео решил быстро, так как уже встречал такую раньше, но зайдя на 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%
Отлично вышло! Благодарю за решение
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
}
Топ материал🔥
Спасибо большое за видео!)
Я решил пойти через рекурсию и понервничал)
вот решение:
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))
Сурово! :) тоже занервничал
Подскажите, значение arr.length откуда берётся, оно же не указано?
Я обычно делаю так. В цикле беру 2 случайных элемента и меняю их местами (а не как у автора перебор массива от конца к началу). В чём разница? А в том что я задаю количество итераций в цикле как захочу. Если мне нужно перемешать как у автора то достаточно сделать количество итераций в цикле равным половине длины массива. Но если мне нужно перемешать массив только ЧУТЬ-ЧУТЬ то я задаю меньшее число итераций чем половина длины массива. Можно задать число итераций и больше чем половина длины массива для "более крутого" перемешивания. Но это не имеет практического смысла.
Развлёкся :)
const shuffle = (arr) => {
const result = []
while(arr.length > 0) {
const rand = Math.random() * arr.length
result.push( arr.splice(rand,1)[0] )
}
return result
}
Отлично! :)
👍
Кстати, кто хочет проверить правильность своей функции, это можно сделать так:
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
распределение должно быть плюс минус одинаковым.
Знакомый код
Вот что получилось, тоже это прям простой вариант
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);
Благодарю за решение!
Интуитивно, мне ваше решение кажется более простым и понятным. Правда, так как это сортировка, то сложность этого лаконичного алгоритма будет уже O(N*log(N))
@@Shtirlic_Isaev Да помимо большей сложности есть еще момент с неравномерным распределением (скажем так не достаточно равномерной рандомности).
@@frontendscience Да, позже прочитал об этом в другой ветке комментариев... И этот эффект значительно интереснее, требует гораздо более глубокого понимания !
Классная задачка,
а вот мое супер неоптимальное решение, решила зачем-то сделать хэш, короче жуть, но вам в копилку комментов:
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))
}
Благодарю за решение! Интнесный вариант вышел! 👍
Добрый день!
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));
Благодарю! Вышло клево!
перед началом видео попробовл свой вариант, и потом понял что опять затупил, сделал переменую для последнего индекса хотя можно было циклом же идти из конца ):
```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
};```
Благодарю за решение!
Вот мой вариант программы, написал его до просмотра решения и возник вопрос: Можно ли использовать вместо (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;
}
Да, прекрасный вариант. Разницы нету, что с начала, что с конца - эффект будет такой же.
Разница будет. Вероятность некоторых исходов больше, чем других (можно проверить циклом). Возможно это из-за того, что начиная сначала числа оставшиеся позади 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,"
Такие дела
ЧтоЖ) Я сделал вот так:
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);
:) Я это называю - "сортировка - загадочная"!
Чёт стрёмно. В документации есть требование, что колбек для одних и тех же элементов должен возвращать одинаковый результат. Иначе сортировка будет неустойчивой (это нас, в данном случае, не парит) и неопределённой по времени, да и вообще, наверное, может выдать ошибку. Самую лучшую из ошибок: которая иногда появляется (не воспроизводимую). Это отдельная мука в аду, фиксить такие ошибки.
Если мы поменяли местами последний элемент с третьим, получается, когда мы дойдем то третьего элемента, то его можно уже не менять, т.к. здесь "рандомно" уже другое значение, которое отличается от входящего массива. Я правильно понимаю?
ну может и так - но если ты его еще раз переставишь то так можно добиться более "высокого уровня" перемешиваемости
@@frontendscience
А я прям задумался... если функцию, основанную на Math.random(), вызвать дважды... будет ли результат более рандомный? Ведь эта функция не выдает абсолютно рандомное число, а вычисляет его как-то, и будет ли второй результат "более рандомный" чем первый? Как вообще можно измерить рандомность результата... И как можно написать свою функцию, выдающую рандомное число, кроме как с привязкой ко времени.
Есть над чем подумать вместо сна :)
Не понял зачем умножать на i+1 (let rnd = Math.floor(Math.random() * (i + 1))). Получается, что чем ближе к нулевому элементу тем меньше шансов стать этому элементу в конец массива?
Нет. Распределение равномерное. Вот тут можно подробней почитать про рандомное целое число в определенном диапазоне. 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
@@frontendscience А в чем преимущество идти с конца массива, а не с начала? от 0 до array.length? В чем профит?
@@bibblebabl ни в чем ) Можно инвертировать все и идти с начала массива - эффект будет тот же. Почему везде в книгах этот алгоритм приводится именно с началом в конце - не знаю. Видать так исторически сложилось.
@@frontendscience исторически сложилось из-за того, что бытует мнение, будто обход массива из конца в начало быстрее
а если касательно именно этого алгоритма: могу предположить, что проходя массив в обратном порядке, на каждой итерации нужно выбирать случайное число в диапазоне [0, i], а не [i, arr.length], что выглядит чуть лаконичнее и требует меньше операций (но тоже такая себе оптимизация)
Учу 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
Благодарю за решение
Интересный алгоритм. Пару мыслей по поводу:
- Мы же не обязаны проходить по всему массиву, мы можем пройти до половины, до трёх четвертей; пройти полтора, два или 42 раза по массиву. Интересно, после какого минимального числа итераций, грубо говоря "степень смешанности массива" уже не увеличивается (и как её вообще определить)?
- Мы же не обязаны брать случайное число от 0 до i, мы можем брать до arr.length. Как это повлияет на перемешивание, и повлияет ли вообще?
Оба вопроса, очевидно, больше к математикам, чем к программистам.
1) Если нужна правильная (равномерная) сортировка, то обязаны. Например, если сортируем 1/5 массива из 10 элементов, то как минимум 6 элементов останутся на своих местах. Если проходить до 1/2 или 3/4 то там все равно есть вероятность у оставшихся элементов быть не сдвинутыми.
2) Вопрос хороший. Я протестировал на большом количестве массивов, у меня в обоих случаях вышел одинаковый результат.
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
методом map возможно решить ?
Нет - через map не выйдет. С помощью map можно заполнить массив рандомными числами например, но перемешать имеющиеся элементы - не выйдет.
спасибо
const mockData = [1,2,3,4,5,6,7]
const shuffle = (incomingArray, resultArray = []) => {
if (incomingArray.length === 0) {
return resultArray
}
const randomItem = Math.floor(Math.random() * incomingArray.length);
resultArray.push(incomingArray[randomItem])
incomingArray.splice(randomItem, 1);
return shuffle(incomingArray, resultArray)
}
console.log(shuffle(mockData))
Благодарю за решение!
array.sort((a, b) => Math.random() > 0.5 ? 1 : -1)
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));
}
}
А как же функциональное программирование с его иммутабельностью?) Изначальный массив изменяется внутри функции, что не есть хорошо.
Для чего не хорошо? Для массива с огроменным объемом данных? Это задачи совсем не про иммутабельность - цена которой память и скорость.
@@frontendscience давно фронтендеры занимаются обработкой огроменных массивов данных?)
Любые мутации в процессе работы программы , потенциально, вызывают лишь геморрой, с которым после вас будет кто-то бороться и искать его, ценой в пару Кб оперативной памяти (не говорим о системах, которые обрабатывают огромные массивы данных, где пренебрежение этим вполне обоснованно, канал про фронтенд).
@@АлександрОхременко-н8й Фронтенд бывает разный) Он не только такой, как в Ваших фантазиях. Если Вы для себя определили уже Вашу зону компетенции и зону развития - не учите алгоритмы. Выбор всегда за Вами.
@@bohdanHutorIT Именно! Надо учитывать контекст! Конкретно в этом случае мы решаем задачи с Leetcode (попутно изучаем различные алгоритмы). На Leetcode для всех задач необходимо найти наиболее оптимальное решение как по времени, так и по памяти.
Я сначала думал из массива брать подряд числа и в зависимости от того что покажет рандом либо добавлять их в начало, либо добавлять в конец массива
Еще вариантик решения. Можно на листочке написать числа, положить их в шляпку и бабка какая-нибудь пусть вытягивает и называет номерки.
почему бабка то
@@inna1305чтобы пенсионерка не скучала
у меня блин не получилось. я даже не догадался как сделать через метод sort, но теперь понял как делать через фишера
Не понимаю, зачем нам нужно умножать на i+1 рандомное число
Функция рандом выводит рандомное число оно выглядит так 0
Дякую
В субтитрах мне пишет: "с вами Сергей Пузырьков..." Ну, думаю, юморист, Серёга. Но нет, это ИИ юморит😂 хотя сортировки пузырьком тут, скорее всего, не будет 🤔
Смешная шутка! 😂
мда уж, если бы на собесах такие задачи были :(
В смысле? :) Так они и бывают на собесах - поэтому мы эту рубрику и ведем)
Мне лично в 2015 году на собеседовании дали эту задачу.
Присылайте задачи, которые попадались Вам.
Лучше бы исходный массив не мутировать =)
Лучше, но тогда сложность по памяти будет O(n) а не O(1) ;)
Ну такое, если задача ставиться отсортировать массив, то он сортируется на месте, это довольно логично. То же самое и с перемешиванием, довольно ожидаемое поведение. Другое дело, что это должно быть оговоренно в требованиях изначально.
@@ИмяФамилия-э4ф7в На Leetcode во всех задачах необходимо найти решение наиболее оптимальное как по времени, так и по памяти.
@@frontendscience это тут ни при чём. Требование мутировать или не мутировать входные данные внешнее по отношению к задаче. Т.е. в условии должно быть либо "вернуть новый массив, который ..." либо "перемешать данный массив..." А вот как реализовать указанное поведение оптимально по времени и по памяти - это вопрос задачи.
@@ИмяФамилия-э4ф7в Для того чтобы не мутировать входные данные, их необходимо будет скопировать. И это значит, что уже по памяти сложность будет O(n), а не O(1). Причем тут Ваш комментарий? У задачи есть четкие требования.
Если точно знать что значения только int то можно избавится от tmp переменной
Даже если можно избавиться - ч в решениях часто делаю избыточные переменные в угоду читаемости и для лучшего понимания что происходит в коде. К счастью на результирующую сложность это не особо влияет.
Ну, блин, что за выражение ОТСОРТИРОВАНО в случайном порядке???? Да не отсортировано, а ПЕРЕМЕШАНО случайным образом. Я уже с перепугу подумал что можно сортировать массивы в убывающем или возрастающем порядке с помощью рандома.
Ну вообще то есть такое выражение отсортирован в случайном порядке. Это и есть принцип сортировки - случайный порядок. Кстати когда-то видел вариант когда в функции sort, рандомным образом выбиралось -1,0,1 :)
Можно сортировать, не вижу проблем. Перемешиваешь, проверяешь: если для каждого i arr[i] >= arr[i+1] то возвращаем результат, если нет, то снова перемешиваем...
По-моему, этот алгоритм лежит в основе работы Windows, visual studio, android studio и т.п. Но это не точно...
вообще можно, алгоритм называется bogosort (эзотерический алгоритм, больше для фана, чем для реальной пользы)
не глядя решение
[1,2,3,4,5].sort(()=>Math.floor(Math.random()*10) % 2 || -1)
а почему атор не упомянул эту версию ?
const shuffle = (arr) => arr.sort(() => 0.5 - Math.random());
@@hakobandreasyan8239 потому что мы мутируем arr, нужно [...arr]
Оно должно получиться больше по сложности, тк алгоритм сортировки внутри js в таком случае делает больше итераций) В документации напрямую просят не использовать конструкцию, возвращающую неопределенный результат, тк, кроме неустойчивого времени выполнения, могут быть выброшены неожиданные исключения
@@andreylomakin6353 оно ж просто возвращает, не мутирует....🤔