Мастер карт: Играя по «алгоритму перетасовки», Госпожа Удача улыбается (*^_^*)

алгоритм JavaScript опрос
Мастер карт: Играя по «алгоритму перетасовки», Госпожа Удача улыбается (*^_^*)

«Эта статья участвовала в мероприятии Haowen Convocation Order, щелкните, чтобы просмотреть:Двойные заявки на внутреннюю и внешнюю стороны, призовой фонд в 20 000 юаней ждет вас, чтобы бросить вызов!"

Чтобы выполнить предыдущую статью:Когда я понимаю проблему P/NP, у меня возникает иллюзия, что я коснулся потолка человеческого познания? !

Наш сегодняшний мир по-прежнему основан наП ≠ НП, так что есть основания полагать, что:Пока мы достаточно перетасуем колоды, удача может прийти.(Жизнь похожа на League of Legends, просто игра на удачу~)

102300016s4n007o28on.gif

В этой статье рассказывается: как достаточно перетасовать карты.Алгоритм перемешивания!

От бронзы до короля, его можно использовать в интервью и реальном бою! Лайк и избранное ✨

Никаких сплетен, просто дайте это прямо! !

Бронзовая перетасовка 🤬

Вопрос: Учитывая новую колоду игральных карт (54 карты), как вы"мыть беспорядок"Это? ?

Мы, бронзовые игроки, обычно сварливы!

Разве это не просто перетасовка! Умные бронзовые игроки, сначала абстрагируйте проблему в алгоритмическую модель!

Проблема переводится как:

Известно: массив nums = [1,2,3,4,5,...,51,52,53,54], решение: новый массив radomNums вышел из строя. (лучше уже некуда)

затем используйте【Извлечение насилия】

Случайным образом сгенерируйте целое число от 1 до 54, затем поместите его в новый массив, а затем случайным образом сгенерируйте целое число. Если оно не повторяется с предыдущим, поместите его непосредственно в новый массив. Если оно повторяется с предыдущим, затем случайным образом сгенерируйте его снова. Один ......

Таким образом, пока все числа в массиве не будут извлечены и помещены в новый массив, решение наконец получено!

Код:

// 生成 nums：
let nums=[]
for(let i=1;i<=54;i++){
    nums.push(i)
}

// 青铜洗牌算法：
let count = 0 
const shuffle = function(nums) {
    let radomNums = []
    while (radomNums.length < nums.length) {
        count++; // count 计数洗牌次数
        let rand = randOne()
        if(radomNums.includes(rand)){ // 随机数重复
            rand = randOne() // 再次生成
        }else{
            radomNums.push(rand)
        }
    }
    return radomNums
}

// 在 1 至 54 之间任意取一整数；
const randOne= function() {
    return Math.floor(Math.random() * 54) + 1;
}

console.log(shuffle(nums))
console.log(count)
// (54) [22, 48, 13, 23, 15, 12, 18, 50, 5, 28, 27, 52, 46, 16, 40, 6, 33, 9, 41, 30, 54, 14, 36, 53, 17, 2, 11, 37, 42, 3, 8, 21, 25, 20, 34, 32, 35, 4, 43, 26, 38, 24, 10, 45, 31, 49, 44, 19, 51, 7, 1, 39, 47, 29]
// 271

Совершенные ~ бронзовые игроки яростно тасуются, просто и прямолинейно, прямо в Союзе! !

Серебряный шаффл 📍

Серебряный игрок смотрел на работу бронзового игрока и не мог сдержать смех!

"Безумная линия~" (sb)

Скопируйте приведенный выше код в консоль для запуска и обнаружите, что для перетасовки этой колоды карт в основном требуется от 200 до 300 тасовок! Потому что чем дальше назад, тем больше вероятность повторения генерации случайных чисел!

Только сумасшедшая линия будет стирать столько раз~

Итак, серебряные игроки начали действовать! дистанционное зондирование

Ключевые слова:【Обмен позициями】.

Случайным образом разделите карты на две стопки, дайте им поменяться местами, затем случайным образом разделите их на две стопки, позвольте им поменяться местами, а затем случайным образом разделите их на две стопки... После повторения тасования десять-двадцать раз тасование завершается.

На самом деле, в действительности, когда мы играем в карты, большинство игроков тасуют так, это еще называется [индийский метод тасования] (это придумал Асан?)

0.gif

Код:

// 生成 nums：
let nums=[]
for(let i=1;i<=54;i++){
    nums.push(i)
}

// 白银洗牌算法：
const shuffle = function(nums){
    let radomNums = JSON.parse(JSON.stringify(nums))
    for(let i = 0;i < 20;i++){
        let randIndex1 = randOneIndex()
        let randIndex2 = randOneIndex()

        if(randIndex2 < randIndex1){ // 若 rand2<rand1，二者替换
            randIndex1 = randIndex1 + randIndex2
            randIndex2 = randIndex1 - randIndex2 
            randIndex1 = randIndex1 - randIndex2
        }

        let radomBlock = radomNums.slice(randIndex1,randIndex2 + 1)
        radomNums = radomNums.slice(0,randIndex1).concat(radomNums.slice(randIndex2,53)).concat(radomBlock)
    }
    return radomNums
}

// 在 0 至 53 之间任意取一整数作数组下标；
const randOneIndex= function() {
    return Math.floor(Math.random() * 54);
}

console.log(shuffle(nums))
// (54) [30, 9, 7, 28, 29, 39, 45, 46, 47, 48, 49, 50, 51, 52, 24, 25, 26, 27, 40, 42, 43, 44, 38, 31, 14, 8, 41, 22, 32, 19, 20, 1, 2, 10, 11, 12, 13, 16, 15, 53, 23, 3, 4, 5, 6, 21, 17, 18, 33, 34, 35, 36, 37, 42]

Серебро, всегда бросай Бога! Перетасуйте карты всего за 20 перетасовок!

Золотое перемешивание 💡

В это время золотой игрок снова засмеялся:«Ха-ха, ты, подонок серебристый, ты совсем не понял названия!»

«Вы понимаете самую критическую проблему перетасовки?"мыть беспорядок"Каково значение этих двух слов? ! "

Перетасовка золота, чтобы узнать ответ:

Случайный результат должен охватывать все ситуации, а вероятность появления случайного результата одинакова;

Перемешайте 54 карты, случайный результат должен охватывать все ситуации, это должно быть расположение 54 карт, A5454, то есть 54!(54 уровня) случайных исходов.

Поменяй местами два на два:

После 1 стирки вы получите n возможных результатов;

После 2 стирок вы получите n*(n-1) видов результатов;

После 3-кратной стирки вы получите n*(n-1)*(n-2) результатов;

......

После n стирок мы довольны:Случайные результаты [перезаписываются все ситуации] и все случайные результаты [вероятность равна].

Таким образом, чтобы достичь цели, его нужно промыть 54 раза.

Код:

// 生成 nums：
let nums=[]
for(let i=1;i<=54;i++){
    nums.push(i)
}

// 黄金洗牌算法：
const shuffle = function(nums) {

    // 高手都用 slice(0) 复制数组
    const radomNums = nums.slice(0);
    let n = radomNums.length;

    // 产生的结果有 n! 种可能
    for (let i = 0; i < n; i++) {

        // 从 i 到 n-1 随机选一个
        const rand = randOne(i, n - 1); 

        // 交换nums数组i和rand下标的两个元素
        [ radomNums[i], radomNums[rand] ] = [ radomNums[rand], radomNums[i] ];
    }

    return radomNums;
};

// 获取闭区间 [n, m] 内的一个随机整数
const randOne= function(n, m) {
    return Math.floor(Math.random() * (m - n + 1)) + n;
};


console.log(shuffle(nums))
// (54) [39, 40, 11, 35, 1, 47, 33, 9, 44, 32, 31, 45, 41, 4, 51, 42, 8, 10, 16, 14, 18, 17, 13, 6, 34, 53, 48, 5, 15, 22, 38, 37, 49, 43, 3, 20, 26, 52, 30, 19, 7, 50, 12, 21, 46, 36, 23, 27, 28, 25, 2, 29, 24, 54]

Платиновый шаффл 🤣

Платиновый бог, сидящий в интернет-кафе, видит этих братьев наверху и смеется, как свинья~~~

Пока вы выходите в интернет и изучаете некоторые стратегии, вы не услышите о проблеме тасования карт.Fisher-YatesАлгоритм перемешивания!

Идеи:

Случайным образом сгенерируйте целое число от 1 до 54 и замените его последним битом массива;

Затем сгенерируйте случайное целое число от 1 до 53 и замените его предпоследней цифрой массива;

Затем сгенерируйте случайное целое число от 1 до 52 и замените его третьей последней цифрой массива;

......

Пока случайное целое число (т.е. 1) не будет сгенерировано между 1 и 1, замените его первым битом массива (т.е. замените себя);

IdW3Yw.md.png

Таким образом, временная сложность равна O(n), а вероятность появления любой карты равна 1/52, что удовлетворяет условию: случайные результаты охватывают все ситуации, а вероятность появления случайных результатов одинакова!

Математическое доказательство: Вероятность того, что карта окажется на i-й позиции, равна P, тогда P будет равняться первым i-1 позициям, которые не взяли эту карту, и i-й позиции взяли эту карту.

IdWw1W.png

Код:

// 生成 nums：
let nums=[]
for(let i=1;i<=54;i++){
    nums.push(i)
}

// 铂金洗牌算法：
const FYShuffle = function (nums) {

    const radomNums = nums.slice(0);
    let len = radomNums.length;
    
    while (len > 1) {
        let rand = Math.floor(Math.random() * len);
        len--;
        let temp = radomNums[len];
        radomNums[len] = radomNums[rand];
        radomNums[rand] = temp;
    }

    return radomNums;
}

console.log(FYShuffle(nums))
// (54) [47, 17, 33, 13, 37, 26, 20, 39, 45, 44, 25, 40, 49, 7, 36, 38, 6, 15, 31, 18, 52, 46, 28, 11, 43, 1, 22, 19, 53, 9, 14, 27, 35, 8, 51, 42, 50, 2, 23, 5, 30, 54, 4, 21, 29, 16, 10, 24, 48, 34, 32, 12, 41, 3]

Алмазная перетасовка 😎

Алмазный Бог похлопал по столу, встал и воскликнул:Перетасовка ласточкиного хвоста (Riffle Shuffle) — это навсегда!

На самом деле так поступают многие игроки в покер высокого уровня (картинка стоит тысячи слов).

127614630_14271639688491n.gif

Принцип: Разделите массив на два, затем перемешайте и объедините, а затем повторите эту операцию;

IdnLHG.md.png

исследование показывает:Метод перетасовки «ласточкин хвост» [перетасовать семь раз] — самый эффективный способ перетасовки!(Кто проводил исследование? Погуглите сами)

Код:

// 生成 nums：
let nums=[]
for(let i=1;i<=54;i++){
    nums.push(i)
}

// 钻石洗牌算法：
const RShuffle = function (arr) {

    let radomNums = nums.slice(0);
    for(let i = 0;i < 7;i++){
        let randIndex = randOneIndex()
        let arr1 = radomNums.slice(0,randIndex)
        let arr2 = radomNums.slice(randIndex,55)
        radomNums = aryJoinAry(arr1 ,arr2)
    }
    return radomNums;
}

// 两个数组穿插合并
const aryJoinAry = function (ary,ary2) {
    var itemAry=[];
    var minLength;
    //先拿到两个数组中长度较短的那个数组的长度
    if(ary.length>ary2.length){
        minLength=ary2.length;
    }
    else{
        minLength=ary.length;
    }
    //将两个数组中较长的数组记录下来
    var longAry=arguments[0].length>arguments[1].length?arguments[0]:arguments[1];
    //循环范围为较短的那个数组的长度
    for (var i = 0; i < minLength; i++) {
        //将数组放入临时数组中
        itemAry.push(ary[i]);
        itemAry.push(ary2[i])
    }
    //itemAry和多余的新数组拼接起来并返回。
    return itemAry.concat(longAry.slice(minLength));
}


// 在 0 至 53 之间任意取一整数作数组下标；
const randOneIndex= function() {
    return Math.floor(Math.random() * 54);
}

console.log(RShuffle(nums))
// (54) [1, 4, 19, 2, 38, 51, 6, 37, 15, 9, 45, 43, 7, 52, 16, 21, 39, 53, 24, 26, 44, 54, 40, 5, 32, 10, 46, 22, 33, 27, 3, 11, 18, 28, 47, 12, 17, 29, 8, 13, 41, 30, 48, 14, 34, 31, 20, 23, 49, 35, 25, 42, 50, 36]

Мастер Шафл 😏

Увидев это, мастер улыбнулся, не говоря ни слова.

Мастер сказал:«Важно перетасовать карты, но можете ли вы раздать карты, которые хотите, после перетасовки?!»

- Хозяин, я понял! Разве это нелотерейный пулХорошо! !

Id5SjT.th.png

Цель: после перетасовки 54 карт вероятность выпадения интервала [1,10] равна 40 %, вероятность выпадения интервала [11,20] равна 20 %, а вероятность выпадения интервала [21,30] равна 20%%, вероятность дотянуть до интервала [31,40] 15%, а вероятность дотянуть остальные до [41,54] 5%;

Идея: мы выводим массив вероятностей, реализуя неупорядоченный массив.

radomNums = [21,43,12,3,...,8,6,33] // 共 54 项

probabilityNums = [0.02,0.015,...,0.04,0.04,0.15] // 共 54 项，和为 1

Затем извлеките стоимость сделки со следующей случайной вероятностью:

function randomProbability(arr1, arr2) {
      var sum = 0,
      factor = 0,
      random = Math.random();
      for(let i = arr2.length - 1; i >= 0; i--) {
        sum += arr2[i]; // 统计概率总和
      };
      random *= sum; // 生成概率随机数
      for(let i = arr2.length - 1; i >= 0; i--) {
        factor += arr2[i];
        if(random <= factor) return arr1[i]; // 如果在当前的概率范围内，得到的就是当前概率，返回输出
      };
      return null;
}

const yourCard = randomProbability(radomNums, probabilityNums)

console.log(yourCard)

Король перетасовка 👑

В это время я увидел спину царя, который был на высоте. Он медленно обернулся. Указывая на высшую тайну тасовки со скипетром в руке:случайная функция! Свято и торжественно!

Задумывались ли вы когда-нибудь, что за механизм случайной функции используется повсеместно?

Если мы взламываем правила генерации случайной функции, значит ли это, что мы взламываем случайность!

ES5 объясняет случайную функцию следующим образом:

15.8.2.14 random ( )

Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

Простым переводом является то, что функция random() создает значение между [0,1) спримерно однородныйраспределение без параметров.

Дальнейшее понимание, под движком Windows chrome V8, браузер, наконец, вызываетфункция rand_s, rand_s — это генератор случайных чисел с достаточно сильной случайностью, обеспечиваемой системой Windows. В других системах также получают высокоточные случайные числа на основе текущей системы. так,Основным источником случайности является возможность полагаться на операционную систему.

Однако MDN по-прежнему говорит, что Math.random — этоПсевдослучайное число, это не безопасно. Из исходного кода V8 мы видим, что источником значения Math.random является /dev/random, что составляет 64 бита, а возможное количество значений равно 2 ^ 64. Случайный алгоритм относительно прост, просто обеспечить как можно более случайное распределение.

Разве 2 в 64-й степени недостаточно? Правильно, не хватает! Имейте в виду, что полная перестановка из 54 карт, 54!(иерархия), намного больше, чем она. Поэтому он пока не может охватить большое количество комбинаторных сценариев.

Что ж, в этом мире естьистинное случайное число? Король улыбается~

В настоящее время считается, что настоящие случайные числа необходимо собирать из реального мира, напримерrandom.orgЭтот веб-сайт генерирует случайные числа, собирая атмосферный шум. 😮

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

Надо сказать, что генерация действительно случайных чисел — очень важная вещь. По крайней мере мир еще не подтвердилП ≠ НПслучае это имеет смысл! !

Идеальный мир 🌅

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

Обычно мы понимаем так много алгоритмов сортировки, и мы должны понимать алгоритм перетасовки (алгоритм вне порядка).

Представьте, если вы Бог, в человеческом обществе, которое вы создали, вы хотите, чтобы человеческая группа часто запутывалась и запутывалась, как бы вы разрушили различные факторы? Как бы люди ни старались, они не увидят, что ты нарушаешь правила, может быть, это может сделать только Бог~

Возможно, процесс нашего постоянного масштабирования точности — это процесс следования правилам познания Бога…

Так же, как Бен Гуа всегда думал, что 1 секунда — это 1 секунда, не зная, что на самом деле она определяется как: время, необходимое для 9192631770 собственных микроволновых колебаний атома цезия...

хорошо, выше это обмен. Есть идея, и мы еще обсудим порядок и беспорядок, рациональные и иррациональные числа и вопросы P/NP в будущем~

tcaQQgK54P9EoJkVxkOMXoSiCXdvluNM.gif

Приветствую всех лайкать👍 подписывайтесь👀комментарии💬

Я Энтони Наггетс, вывод раскрывает информацию, техническое понимание жизни, до свидания~

Категории