Пятничный JS: случайное перемешивание

    Экзамен в школе прапорщиков.
    — Вот смотрите. Это большой палец, это — указательный, это — средний, это — безымянный, это — мизинец. Мешаем, мешаем, мешаем (двигает пальцами)… Теперь где какой?
    Всем привет. С ортодоксальной точки зрения сегодня не настоящая пятница — просто день, когда завтра выходной. Поэтому статья в моей традиционной рубрике тоже будет не совсем настоящая, у неё пониженный градус безумия и повышенная полезность. Однако довольно предисловий, перейдём к сути.

    Перед моими студентами регулярно встаёт задача случайного перемешивания массива. За её решением они, как правило, лезут в гугл. И гугл им подсказывает следующее:

    var shuffledArr = arr.sort(function(){
      return Math.random() - 0.5;
    });
    

    Здесь и далее будем называть этот метод случайной сортировкой. Сегодня я решил написать о том, какие преимущества и недостатки есть у такого подхода.

    Как это вообще работает?


    Метод sort у джаваскриптовых массивов в качестве аргумента принимает функцию-компаратор. Эта функция должна принимать два элемента массива и возвращать число. Если число положительное, алгоритм сортировки считает, что первый элемент больше; если отрицательное — значит, первый элемент меньше; если же компаратор возвращает нуль, то в рамках данной сортировки элементы как бы равны. Если под видом компаратора передать функцию, которая будет возвращать положительное или отрицательное число случайным образом, то массив окажется отсортирован в «случайном» порядке.

    Преимущества


    Такое перемешивание очень быстро пишется. Я честно пытался придумать какое-нибудь ещё преимущество, но мне не удалось.

    Недостатки


    Этот параграф будет несколько длиннее, потому я разобью его на подпараграфы.

    Несоответствие спецификации


    Спецификация EcmaScript (я намеренно не называю версию, поскольку во всех версиях этот пункт остаётся примерно одинаковым) заявляет нам следующее:
    If comparefn is not undefined and is not a consistent comparison function for the elements of this array (see below), the sort order is implementation-defined.

    В переводе с технического английского на русский разговорный это означает, что если компаратор не отвечает некоторым очевидным требованиям (ниже в спецификации разъясняется, что, в частности, он должен для одних и тех же аргументов всегда возвращать одно и то же значение), то порядок сортировки зависит от реализации конкретного джаваскриптового движка. То есть, фактически, не определён. Разработчик браузера имеет, например, полное право сделать так, что при обнаружении того, что компаратор «ненастоящий», возвращается исходный массив без каких-либо перестановок. И это будет полностью соответствовать спецификации. То, что во всех существующий браузерах приведённый метод даёт нечто похожее на случайное перемешивание — не более чем счастливое совпадение.

    Временна́я сложность


    Корректный алгоритм перемешивания (см. ниже) имеет временную сложность O(n). Попросту говоря, это означает примерно следующее: если длина массива увеличится в 10 раз, то продолжительность его перемешивания также увеличится в 10 раз.

    Самые быстрые алгоритмы сортировки имеют временную сложность O(n*log(n)). Это означает, что при увеличении длины массива в 10 раз продолжительность его перемешивания увеличится более чем в 10 раз.

    В сумме эти два факта значат вот что: для достаточно большого массива перемешивание случайной сортировкой будет работать медленнее, чем «правильное» перемешивание (даже если для маленьких массивов это было не так). И чем больше массив, тем больше разница во времени выполнения.

    Почему я сделал оговорку в скобках? Потому что Array#sort выполняется нативным кодом, и за счёт этого на небольших массивах потенциально может оказаться быстрее. У него может оказаться меньше константный множитель, сказал бы человек, знакомый с О-нотацией.

    Ненастоящая случайность


    Те, кто хотя бы поверхностно знаком с теорией вероятностей, знают, что случайность случайности рознь. Монетка может выпасть орлом или решкой, кубик может выпасть шестёркой или не шестёркой. И там, и там имеют место случайные события, однако в первом случае события равновероятны, а во втором нет.

    Перемешивание массива называется истинно случайным, если все возможные перестановки его элементов имеют одинаковую вероятность. Именно этим свойством случайная сортировка не обладает, и я покажу это на практике.

    Я набросал следующую страничку. На ней находятся две диаграммы, одна соответствует случайному перемешиванию, вторая — случайной сортировке. Впрочем, вы сейчас видите не диаграммы, а квадратики, разбитые на клеточки различных оттенков серого. Чтобы они стали диаграммами, нужна легенда — объяснение, что эти клеточки и их цвета означают. Всё очень просто. Мы несколько раз (в данном случае несколько = 10000) берём массив чисел от 0 до n (в данном случае n = 32) и случайно перемешиваем тем или иным алгоритмом. Затем мы вычисляем частоты, с которыми то или иное число оказывается на том или ином месте. Соответственно, цвет клетки в строке номер i и столбце номер j показывает, насколько часто число i оказывается на месте j. Чёрный цвет означает, что оно там не оказывается никогда, белый — что оно там оказывается вдвое или более чаще, чем положено. Если число попадает на указанное место с теоретически предсказанной частотой 1/n, клетка будет иметь цвет hsl(0, 0%, 50%) — оттенок серого, расположенный в точности посередине между чёрным и белым.

    Если вы используете свежую версию браузера Chrome, вы видите, что в квадрате справа много белых или почти белых клеток, расположенных по определённой закономерности. Это означает, что при случайной сортировке определённые элементы имеют тенденцию оказываться в определённых местах. Плохо ли это? Зависит от того, для чего вы используете перемешивание. Если для каких-то косметических эффектов, то, возможно, ничего страшного. Если вам важно, чтобы пользователь не мог предсказать, какой элемент окажется на каком месте, или если закономерности в перемешивании каким-то образом заметны визуально — то плохо. И упаси вас Гермес использовать такое перемешивание для чего-то, связанного с криптографией.

    Что удивительно, если вы используете Firefox, то для вас оба квадрата примерно одинаково серые. Это происходит оттого, что в разных браузерах используются различные алгоритмы сортировки (если интересно, вот моя статья на эту тему). В таком случае, если хотите удивиться ещё раз, допишите в адресной строке ?size=8 (вот готовая ссылка для ленивых). Firefox по-разному сортирует большие и маленькие массивы, сюрприз!

    Upd: товарищ mk2 заметил, что равномерно-серым квадрат в Firefox будет только при размере, равном степени двойки. Нужно больше таких внимательных товарищей, товарищи!

    Upd2: товарищи Stalker_RED и yaZva не поленились (в отличие от меня) сделать скрины в различных браузерах.

    Напоследок добавлю, что вот эти мои диаграммы с пятьюдесятью оттенками серого — не критерий, а признак. Из того, что квадрат получился не серый, следует, что сортировка не равномерна, однако неверно обратное. Контрпример — циклический сдвиг на случайную величину. Частоты попадания элементов на места будут совершенно одинаковы, однако ни о какой истинной случайности перемешивания, разумеется, не может быть и речи.

    Upd3: в этой ветке обсуждается, почему случайная сортировка не даёт равномерную случайность в Firefox (причём даже в том случае, если по диаграмме кажется, что даёт).

    Как правильно?


    Истинные джедаи используют одну из вариаций алгоритма Фишера-Йетса. Для своей демки я реализовал его так:

    function shuffle(arr){
    	var j, temp;
    	for(var i = arr.length - 1; i > 0; i--){
    		j = Math.floor(Math.random()*(i + 1));
    		temp = arr[j];
    		arr[j] = arr[i];
    		arr[i] = temp;
    	}
    	return arr;
    }

    Суть алгоритма, если перевести с JS на русский, следующая: берём последний элемент и меняем его местами со случайно выбранным элементом не правее его (в том числе, возможно, и с ним самим). Затем повторяем ту же операцию для предпоследнего элемента, потом для предпредпоследнего и так далее. Вуаля! (этим словом с JS на русский переводится «return arr;»).

    Настало время безумия


    Кто-то из читателей ждал этого целую статью, остальные, в принципе, могут этот параграф не дочитывать. Я задался вопросом: можно ли написать такую функцию compare, что arr.sort(compare) даст истинно случайную перестановку? Ответ: можно, но с определёнными оговорками. Первая — функцию надо перед каждой сортировкой создавать заново. Вторая — в массиве не должно быть одинаковых элементов. Итак, узрите:

    //вспомогательная функция
    function putToCache(elem, cache){
    	if(cache.indexOf(elem) != -1){
    		return;
    	}
    	var i = Math.floor(Math.random()*(cache.length + 1));
    	cache.splice(i, 0, elem);
    }
    //функция, возвращающая свеженький, девственный компаратор
    function madness(){
    	var cache = [];
    	return function(a, b){
    		putToCache(a, cache);
    		putToCache(b, cache);
    		return cache.indexOf(b) - cache.indexOf(a);
    	}
    }
    //собственно функция перемешивания
    function shuffle(arr){
    	var compare = madness();
    	return arr.sort(compare);
    }
    

    Это работает следующим образом: при создании компаратор через замыкание получает доступ к массиву cache. Каждый раз, когда ему передаются аргументы, он кладёт их в cache на случайные места (если их там ещё нет), а затем считает, что тот элемент, который в cache стоит правее, будет больше. То есть по сути в массиве cache постепенно строится тот случайный порядок, в котором элементы должны стоять, а метод sort постепенно приводит исходный массив в соответствии с этим порядком. Если же в нём окажутся равные элементы (равные с точки зрения оператора ===, если мы сортируем объекты — то всё хорошо, даже если у них одинаковое содержание. {a: 1} !== {a: 1}), они, к сожалению, будут идти подряд.

    На этом всё. Спасибо за чтение, надеюсь, вам было познавательно, и особенно надеюсь, что я убедил вас не использовать случайную сортировку почти никогда. Приятного грядущего вечера.
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 68
      +7

      А мне кажется или это правда что теоретически возможны случаи (в зависимости от использованного алгоритма сортировки), когда [1,2,3].sort(() => Math.random - 0.5) не завершится никогда (потому что сортировка не стабильна), ну или будет работать неопределенно большое время.

        +6
        Я бы ответил так: теоретически, можно написать такой алгоритм сортировки, который на случайном компараторе будет работать неопределённо долго. Допустим, модифицировав пузырёк, чтобы всплытие на каждой итерации производилось по всей длине массива, а критерием завершения стало отсутствие обменов элементами на последней итерации. Однако из существующих и применяющихся алгоритмов те, которые я сумел вспомнить, не обладают подобным недостатком. Эффективный алгоритм сортировки — это по сути то или иное дерево сравнений. Он не сравнивает элементы по два раза и не сравнивает элементы, отношение между которыми может быть выведено из уже произведённых сравнений. Потому он даже не заметит, что царь не настоящий.
        +1
        SELECT * FROM table ORDER BY RAND() LIMIT 1
        — ещё круче (некоторые так делают выборку случайной строки из таблицы)
          +2
          А как правильно?
            +1
            Сначала вычислить номер, потом получить строку по номеру. На больших таблицах это будет намного быстрее даже несмотря на два запроса вместо одного.
              0
              Перемешивание массива подразумевает, что потом, выбирая последовательно элементы, один и тот же элемент не попадётся дважды (например, номера купонов, ещё и проверить, потом, можно будет, что купон выдан). Каждый раз выбор случайного элемента этого не гарантирует, поэтому, собственно, массивы и перемешивают.
                +2

                Вы точно сейчас говорите про тот запрос с ORDER BY RAND()? Там, если что, нет ни массива, ни последовательной выборки.

                  0
                  Я скорее и о вашем комментарии и о том запросе: что это ситуации не из обсуждаемых в статье. Хотя, если убрать лимит, то как раз получается упорядоченный список, но поскольку порядок хранения строк в таблицах неопределён, то что бы реально это использовать, надо сохранить в таблицу, и кластерный индекс строить по результату или поле добавлять или просто на вывод отдать. Номера не заглядывая в данные таблицы, получить будет быстрей, но если таблица хорошо нагружена на запись, то тут уже вопрос актуальности, впрочем, как и всегда в SQL любой вопрос — не простой.
              +1
              А как правильно?
              Важнее, что не так с этим кодом. Если мне не изменяет память, то вместо быстрого выбора одного случайного элемента вы сначала присваиваете всей таблице случайное число (а там может быть миллионы записей), потом сортируете эту таблицу и потом просто берете первый элемент.
              Представьте, что вам надо выбрать случайную карту. Вместо того, чтобы просто взять случайную карту — вы на каждую запускаете генератор случайных чисел, потом записываете на карте это число, сортируете всю колоду по возрастанию этих чисел и берете первую карту. Представьте, как бы это было долго в сравнении с «просто взять случайную карту»
            0
            Когда-то перемешивал картинки: шёл до половины массива и менял их со случайными элементами второй половины, с поправкой, при нечётном количестве. Воообще, для перемешивания n элементов, надо n/2 обменов, насколько хорошо у меня получилось — не знаю, но явно лучше, чем у Винампа, в своё время. :-)
              0
              Диаграмма бы получилась в виде белого косого креста) А хорошо или нет — опять же, зависит от цели. Возможно, пользователю при частом обновлении страницы надоело бы видеть на первом месте две картинки попеременно.
                0
                А можно увидеть реальную диаграмму, я не вижу, почему элементы в данном случае, будут тяготеть к каким-то местам, хотя, то что качество сортировки не слишком высокое — интуитивно понимаю.
                  0
                  Пардон, невнимательно прочитал. Мне почему-то показалось, что элемент случайно меняется местами с симметричным ему элементом. Не знаю, почему я так прочитал.

                  Сейчас попробую построить диаграмму, так с ходу не соображу, как она должна выглядеть)
                    0
                    В принципе, я уже вижу, что во второй половине, элементы будут чаще оставаться на своих местах, но какая половина проходится последовательно, можно чередовать.
                      0
                      А красиво)
                        0
                        Не слишком ли много никогда не меняющихся элементов? Как-то не вериться, что из второй половины массива никогда не выбиралось 75% элементов.
                          0
                          Белый — это не никогда не меняющиеся, это оказывающиеся на данном месте с вероятностью вдвое или более выше расчётной. Да, немного контринтуитивный способ отображения, но при интуитивном получался недостаточный контраст.
                            0
                            Я как раз про три треугольника чёрного цвета.
                              +1
                              А. Клетки чёрного цвета показывают, какие элементы в какие места никогда не попадут. например, элементы из второй половины массива не могут попасть на другое место во второй половине массива. Либо они остаются на месте, либо перемещаются в первую половину. Элементы первой половины массива могут переместиться во вторую, а потом обратно в первую, но только с повышением номера, а не наоборот. Всё же правильно вроде?
                                +2
                                Абсолютно верно, я просто думал, что учитывается несколько последовательных итераций над всем массивом.
                                  0
                                  Хм. Действительно, в описание эксперимента вкралась неточность. Сейчас попробую переформулировать.
                          +1
                          Кстати, ещё красивее получается, если увеличить число итераций до миллиона.
                          спрячу, чтобы не растаращивать страницу

                            0
                            Кстати, по поводу идеи, что можно чередовать какую из половин проходим последовательно, то если определять это случайным образом, то это не будет мухлежом, потому что это реальная дополнительная вероятность для каждого элемента и картина должна измениться на вашем тесте.
                              0
                              Ну, собственно, картина будет, приблизительно как если на текущую диаграмму наложить её же перевёрнутую с прозрачностью 50%. Чёрные области исчезнут, но неравномерности останутся.

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

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

                              По прочим параметрам алгоритм Фишера-Йетса предпочтительнее.
                                0
                                Кстати, по поводу идеи, что можно чередовать какую из половин проходим последовательно, то если определять это случайным образом

                                Проблема в том, что как только выясняешь, какая половина была выбрана — сразу можно предсказать положение большинства элементов
                    +2
                    но явно лучше, чем у Винампа, в своё время. :-)
                    Это только подтверждает, что «случайность не выглядит случайной», а в Винампе, вероятно, была она.
                    В более новых плеерах добавлены исправления, чтобы «случайное воспроизведение» казалось более случайным.
                      0
                      Насчёт «неслучайной случайности», с последовательностью всё ещё интересней. Есть такой простой тест: выкладывайте карты из колоды по одной и отсчитывайте значение карты, начиная с любой. Отсчитали, берёте новое значение и так до конца колоды, последняя карта почти всегда совпадёт с тем, кто будет считать параллельно с вами (хорошо на детях срабатывает, типа угадаю карту), но начинали вы с разных карт, просто совпадение в любом месте объединяет цепочки, а мест много, поэтому вероятность очень высокая.
                        +2
                        Честно говоря, я не очень понял методологию эксперимента. Можно более подробно?
                          0
                          Карты: валет 2 очка, король 4, тройка 3 и т.п. Карты выкладываются открыто, например серия:
                          2, 4, 3, 6, 9, 2
                          Если человек про себя начал считать с первой карты (он сам решает когда начинать, но желательно в начале процесса), то у него будет 2, 3, 2-это последняя карта, которую и надо угадать. Предполагается, что поскольку первая карта была выбрана случайно, то и последняя будет уникальна. Параллельно с ним кто-то так же начинает отсчёт, тоже с любого места, придут к финишу они скорее всего на одной и той же карте, что бы повысить шансы надо оставить двойки и тройки.
                    +1
                    шёл до половины массива и менял их со случайными элементами второй половины, с поправкой, при нечётном количестве

                    Довольно очевидная, но неправильная и ненужная с точки зрения O(n) оптимизация, т.к. «надо n/2 обменов» — это все-равно время линейное. Такие оптимизации стоит делать только если вы уже профилируете и видите, что реально в этом месте в два раза ускорить и будет замечательно, а качество результата не столь важно. И даже в таком случае можно придумать более непредсказуемые алгоритмы — к примеру хватать только четные элементы и менять их с только-нечеткими.
                    0
                    А есть ли принципиальная разница между направлениями прохода в вашем варианте алгоритма? То бишь цикл запускать не с конца массива, а с начала. И «не левее» соотвественно
                      0

                      По сути нет, просто с конца удобнее записывать.

                      +5
                      На самом деле для firefox у вас удачно совпало, что дефолтный размер массива равен двум. Видимо, там используется mergesort с делением на степени двойки или что-то подобное. Попробуйте size=24 например. Кстати, это наименьший размер, на котором используется этот алгоритм, 23 еще другой)
                        0
                        Тысяча чертей, это вы здорово подметили)
                        0
                        ошибся, был невнимателен
                          0
                          Совершенно верно. Это описано в статье википедии, на которую я ссылаюсь. У меня реализован продвинутый вариант.
                            +1
                            Эх, а я уже стер свой комментарий, т.к. увидел, что у вас продвинутый. Поспешил.
                              +1

                              Кстати, почему не «вывернутый», те. слева на право:


                              function shuffle(list) {
                                for (let i = 0; i < list.length; i += 1) {
                                  const j = Math.floor(Math.random() * (i + 1)); // rand int 0 =< j =< i
                                  [list[i], list[j]] = [list[j], list[i]];
                                }
                                return list;
                              }
                                0
                                Потому что я знаю, как доказывать равновероятность для своего варианта, а для вашего надо ещё раз думать) но вообще да, вроде эквивалентно. (бормочу по-математически) Если перестановку вашего варианта перемножить с моей (предполагая, что случайные числа выпадали те же, но в обратном порядке), получится тождественная перестановка. Одинаковые транспозиции схлопнутся. То есть ваша перестановка будет обратна моей. Если моя равновероятна, то и ваша равновероятна.
                            0
                            В Chrome, если size=512 (и меньше), то можно четко увидеть вертикальную полосу посередине, а при size=1024 несколько мелких белых поперечных крапинок. А при size=4096 исчезает диагональная полоса, видная на меньших размерах.
                            Интересно.
                              +1
                              Полагаю, тут дело не в особенностях сортировки, а в особенностях визуализации. У меня канвасы 512 на 512) скорее всего, если увеличить количество пикселей в канвасе, артефакты исчезнут.
                              +3
                              Я, пожалуй, приложу картинку
                              image
                                +1
                                Ух ты. Опера прикольная) добавил в статью ссылку на этот коммент.
                                +2
                                Microsoft Edge тоже красиво)
                                image
                                  0

                                  Что-то необычное в нём используется для сортировки. Сортирует правда медленнее чем все другие браузеры.

                                    0
                                    Говорят, там модифицированная сортировка вставками до 512 элементов.
                                  0
                                  Суть алгоритма, если перевести с JS на русский, следующая: берём последний элемент и меняем его местами со случайно выбранным элементом не правее его

                                  Мне всегда была непонятна необходимость этого условия. Если менять со случайно выбранным элементом (любым, а не только те, что не правее) — будет ровно такая же равномерная случайность. Можете, пожалуйста, подтвердить это картинкой?
                                    +2
                                    Подтвердить не могу.
                                    Заголовок спойлера

                                      +1
                                      Любопытно. Значит я ошибался, а это тоже важно узнать, спасибо.

                                      Интересно, а кто-то может объяснить, в чем изъян моей логики?
                                        +5
                                        Мне затруднительно это сделать, поскольку мне неизвестен ход вашей мысли. Но я знал, что вы неправы, ещё до того, как запустил симуляцию. В результате n итераций, каждая из которых имеет n возможных равновероятных вариантов перестановки, мы получаем nn равновероятных вариантов перемешивания. В то же время возможных перестановок у нас n!. Чтобы перестановки оказались равновероятны, каждой из них должно соответствовать одинаковое количество вариантов перемешивания. Но nn не делится на n! для n > 3.
                                          0
                                          Звучит чертовски логично, спасибо.
                                            0
                                            Для n == 3 тоже не делится. А так всё верно.
                                              0
                                              Больше либо равно хотел написать, да.
                                        +3
                                        Можете, пожалуйста, подтвердить это картинкой?
                                        Как можно подтведить нечто очевидно неверное картинкой?

                                        В вашем подходе на каждом шаге выбирается один из n исходов. Вы делаете n щагов. То есть получаете nⁿ вариантов. Правда некоторые из них одинаковы (скажем вариант 1, 2, 3, ..., n получится если ничего никуда не двигалось, но также если 1 попадёт на место 2, а потом вернётся и так далее). То есть вероястности у вас в конечном итогде поучаться вида kα/nⁿ. А нужно-то нам 1/n!. Как несложно заметить — это возможно только при n == 1 или n == 2. А для этих двух случаев и так всё понятно.

                                        Мне всегда была непонятна необходимость этого условия.
                                        Без этого условия нет факториала. Без факториала нет гарантированно правильного перемешивания. Всё просто.
                                          0
                                          Да, согласен со всеми вашими аргументами, видимо мне стоило больше подумать перед тем, как задавать тот вопрос.
                                          +2

                                          В 2014 на Google Code Jam даже предлагалась задача, в которой требовалось отличить последовательности сгенерированные правильным и вашим алгоритмом:


                                          https://code.google.com/codejam/contest/2984486/dashboard#s=p2

                                          +3
                                          Раз уж mk2 упомянул merge sort, то, кажется, было бы полезно наглядно продемонстрировать, почему сортировка случайным сравнением не работает. Пусть есть массив [1, 2, 3]. Пройдем самый простой алгоритм сортировки слиянием:
                                          1) разбиваем на списки: [1], [2], [3]
                                          2) сливаем соседние пары, первый слитый список получится честно случайным: [(1|2), (2|1)], [3].
                                          3) а теперь финальное слияние сразу поставит тройку в начало с шансом 50%, и привет, должно было быть ~33%.
                                          То же самое происходит при любых массивах не длины степени двойки: как только сливаются списки разных размеров, последний элемент более длинного имеет больший шанс попасть в конец результата.
                                            0
                                            Мне вот интереснее, для степени двойки получается действительно случайное перемешивание или нет.
                                              +1
                                              Нет. Потому что при слиянии двух списков одинаковой длины вероятность того что первый и последний элементы будут взяты из разных списков больше 1/2.

                                              Кстати, можно попробовать нарисовать картинку как часто элементы с указанными номерами оказываются рядом.
                                                0
                                                Правда ли, что если прогнать merge sort, но при сливании выбирать элемент с вероятностью пропорциональной остатку длины его списка, то получится равномерно случайное перемешивание в итоге? Похоже на то, на длинах 3 и 4 точно работает.
                                                  +1
                                                  Да, правда. Это легко доказывается по индукции. Одна проблема: компаратор про длину списка не знает :-)
                                                    0
                                                    Я пытаюсь как-то строго сформулировать вопрос о том, существует ли сортировка, которая со случайным компаратором даст равномерное перемешивание. Но надо как-то отсечь случай, когда сортировка, допустим, совершает стопицот тестовых прогонов компаратора и дальше действует в зависимости от их результата.
                                                      0
                                                      Если время работы ограничено — то таких сортировок точно не существует. Просто потому что вероятность 1/n! нельзя «набрать» степенями двойки (т.е. представить в виде m/2k).

                                                      Среди алгоритмов с неограниченным временем работы такие сортировки точно есть. Например, Bogosort со случайным компаратором даст случайную перестановку (но затратит на это в среднем O(n 2n) времени!).
                                                        0
                                                        Сортировка с ограниченным временем работы не обязана быть детерминированной. Напримем, квиксорт со случайным выбором опорного элемента. Так что аргумент про степени двойки не канает.
                                                          0
                                                          Хм. Гениально. Сортировка даст равномерное перемешивание со случайным компаратором, если перед сортировкой массив случайно перемешать)))
                                                  +1

                                                  Нет. Представим, что у нас массив [1,2,3,4]. Какова вероятность, что первые да из них будут 3 и 4 в каком-то порядке? 1/4 т.к перемешивание на нижнем уровне не влияет, а при слиянии двух массивов длины 2 нам нужно выбрать второй массив дважды. Какова вероятность должна быть? 4/24=1/6

                                                0
                                                Спасибо, полезно.

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

                                                Самое читаемое