欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JS: 数组乱序

程序员文章站 2022-03-24 14:01:49
数组乱序 顾名思义,数组乱序就是把数组存储的值的顺序都打乱。 Fisher–Yates shuffle 著名的 "洗牌算法" ,原理就是遍历数组元素,将当前元素与随机抽取的一个剩余元素进行交换。 下列表格遍历元素是从后往前: | 随机数范围 | 随机数 | 原始数据 | 结果 | | : : | : ......

数组乱序


顾名思义,数组乱序就是把数组存储的值的顺序都打乱。

fisher–yates shuffle


著名的洗牌算法,原理就是遍历数组元素,将当前元素与随机抽取的一个剩余元素进行交换。

下列表格遍历元素是从后往前:

随机数范围 随机数 原始数据 结果
1 2 3 4 5 6
[ 0 , 5 ] 1 1 6 3 4 5 2
[ 0 , 4 ] 3 1 6 3 5 4 2
[ 0 , 3 ] 1 1 5 3 6 4 2
[ 0 , 2 ] 2 1 5 3 6 4 2
[ 0 , 1 ] 1 1 5 3 6 4 2
[ 0 , 0 ] 0 1 5 3 6 4 2

代码如下:

function shuffle(arr) {
    for (let i=arr.length-1; i>=0; i--) {
        let rindex = math.floor(math.random()*(i+1));
        // 打印交换值
        // console.log(i, rindex);
        let temp = arr[rindex];
        arr[rindex] = arr[i];
        arr[i] = temp;
    }
    return arr;
}

shuffle([1,2,3,4,5,6]); // [1, 5, 3, 6, 4, 2]

现在测试一下是否真的实现了乱序:

// 使用 res 存储结果
let res = {};
let times = 100000;
for (let i=0; i<times; i++) {
    // 使用 [1, 2, 3] 进行简单测试
    let key = json.stringify(shuffle([1, 2, 3]));
    res[key] ? res[key]++ : res[key] = 1;
}
for (let key in res) {
    res[key] = number.parsefloat(res[key]/times *100 ).tofixed(3) + '%';
}
// 从结果可以看出是实现了真正的乱序的
res; 
/*
[1,2,3]: "16.514%"
[1,3,2]: "16.764%"
[2,1,3]: "16.606%"
[2,3,1]: "16.587%"
[3,1,2]: "16.712%"
[3,2,1]: "16.817%"
*/

固定一个值


在乱序的同时,固定一个下标的值,使其位置不变,方法有很多,这里只给出一种:

function shuffle(arr, index) {
    let res = [];
    // 取出固定值
    let fix = arr.splice(index, 1)[0];
    for (let i=arr.length-1; i>=0; i--) {
        let rindex = math.floor(math.random()*(i+1));
        res.push(arr[rindex]);
        arr.splice(rindex, 1);
    }
    // 将固定值放入指定位置
    res.splice(index, 0, fix);
    return res;
}
// 多次运行,可以看出数组下标为 1 的值始终是固定的
shuffle([1,2,3,4,5,6], 1);
// [5, 2, 6, 3, 1, 4]
// [5, 2, 6, 3, 4, 1]
// [3, 2, 4, 6, 1, 5]

这里同样测试一下是否实现了真正的乱序:

let res = {};
let times = 100000;
for (let i=0; i<times; i++) {
    // 使用 [1, 2, 3] 进行简单测试,固定数组下标 1 的值
    let key = json.stringify(shuffle([1, 2, 3], 1));
    res[key] ? res[key]++ : res[key] = 1;
}
for (let key in res) {
    res[key] = number.parsefloat(res[key]/times *100 ).tofixed(3) + '%';
}
// 固定的同时,依然是乱序的
res;
/*
[1,2,3]: "49.976%"
[3,2,1]: "50.024%"
*/

注意


需要注意的是,因为数组是引用类型,所以上面的方法都会改变原数组,要想不改变原数组只需稍稍改动一下代码即可,这个很简单,就不写了。