Hướng dẫn is there a shuffle method in javascript? - có phương pháp xáo trộn trong javascript không?

Shuffle mảng tại chỗ

function shuffleArr (array){
    for (var i = array.length - 1; i > 0; i--) {
        var rand = Math.floor(Math.random() * (i + 1));
        [array[i], array[rand]] = [array[rand], array[i]]
    }
}

Es6 tinh khiết, lặp đi lặp lại

const getShuffledArr = arr => {
    const newArr = arr.slice()
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr
};

---

Kiểm tra độ tin cậy và hiệu suất

Một số giải pháp trên trang này không đáng tin cậy (chúng chỉ ngẫu nhiên một phần cho mảng). Các giải pháp khác ít hiệu quả hơn đáng kể. Với

const getShuffledArr = arr => {
    const newArr = arr.slice()
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr
};

2 (xem bên dưới), chúng tôi có thể kiểm tra các chức năng xáo trộn cho độ tin cậy và hiệu suất.

function testShuffleArrayFun(getShuffledArrayFun){
    const arr = [0,1,2,3,4,5,6,7,8,9]

    var countArr = arr.map(el=>{
        return arr.map(
            el=> 0
        )
    }) //   For each possible position in the shuffledArr and for 
       //   each possible value, we'll create a counter. 
    const t0 = performance.now()
    const n = 1000000
    for (var i=0 ; i{countArr[key][value]++}
        )
    }
    const t1 = performance.now()
    console.log(`Count Values in position`)
    console.table(countArr)

    const frequencyArr = countArr.map( positionArr => (
        positionArr.map(  
            count => count/n
        )
    )) 

    console.log("Frequency of value in position")
    console.table(frequencyArr)
    console.log(`total time: ${t1-t0}`)
}

---

Các giải pháp khác

Các giải pháp khác chỉ để giải trí.

ES6 thuần khiết, đệ quy

const getShuffledArr = arr => {
    if (arr.length === 1) {return arr};
    const rand = Math.floor(Math.random() * arr.length);
    return [arr[rand], ...getShuffledArr(arr.filter((_, i) => i != rand))];
};

ES6 thuần khiết sử dụng mảng.map

function getShuffledArr (arr){
    return [...arr].map( (_, i, arrCopy) => {
        var rand = i + ( Math.floor( Math.random() * (arrCopy.length - i) ) );
        [arrCopy[rand], arrCopy[i]] = [arrCopy[i], arrCopy[rand]]
        return arrCopy[i]
    })
}

ES6 thuần túy bằng cách sử dụng mảng.Reduce

function getShuffledArr (arr){
    return arr.reduce( 
        (newArr, _, i) => {
            var rand = i + ( Math.floor( Math.random() * (newArr.length - i) ) );
            [newArr[rand], newArr[i]] = [newArr[i], newArr[rand]]
            return newArr
        }, [...arr]
    )
}

Giải pháp đơn giản có thể là:

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

let arr = [1, 2, 3];
shuffle(arr);
alert(arr);

Điều đó có phần hoạt động, bởi vì

const getShuffledArr = arr => {
    const newArr = arr.slice()
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr
};

3 là một số ngẫu nhiên có thể dương hoặc âm, do đó, hàm sắp xếp sắp xếp lại các yếu tố một cách ngẫu nhiên.

Nhưng vì hàm sắp xếp không có nghĩa là được sử dụng theo cách này, không phải tất cả các hoán vị đều có cùng một xác suất.

Ví dụ, hãy xem xét mã dưới đây. Nó chạy

const getShuffledArr = arr => {
    const newArr = arr.slice()
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr
};

4 1000000 lần và tính xuất hiện của tất cả các kết quả có thể có:

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

// counts of appearances for all possible permutations
let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join('')]++;
}

// show counts of all possible permutations
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

Một kết quả ví dụ (phụ thuộc vào động cơ JS):

123: 250706
132: 124425
213: 249618
231: 124880
312: 125148
321: 125223

Chúng ta có thể thấy sự thiên vị rõ ràng:

const getShuffledArr = arr => {
    const newArr = arr.slice()
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr
};

5 và

const getShuffledArr = arr => {
    const newArr = arr.slice()
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr
};

6 xuất hiện thường xuyên hơn nhiều so với những người khác.

Kết quả của mã có thể khác nhau giữa các công cụ JavaScript, nhưng chúng ta đã có thể thấy rằng phương pháp này là không đáng tin cậy.

Tại sao nó không hoạt động? Nói chung,

const getShuffledArr = arr => {
    const newArr = arr.slice()
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr
};

7 là một hộp đen của người Hồi giáo: Chúng tôi ném một mảng và một hàm so sánh vào đó và mong đợi mảng sẽ được sắp xếp. Nhưng do sự ngẫu nhiên hoàn toàn của so sánh, hộp đen phát điên, và chính xác nó phát điên như thế nào phụ thuộc vào việc thực hiện cụ thể khác nhau giữa các động cơ.

Có những cách tốt khác để làm nhiệm vụ. Chẳng hạn, có một thuật toán tuyệt vời có tên là Fisher-Yates Shuffle. Ý tưởng là đi bộ mảng theo thứ tự ngược lại và trao đổi từng phần tử với một phần tử ngẫu nhiên trước nó:

function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1)); // random index from 0 to i

    // swap elements array[i] and array[j]
    // we use "destructuring assignment" syntax to achieve that
    // you'll find more details about that syntax in later chapters
    // same can be written as:
    // let t = array[i]; array[i] = array[j]; array[j] = t
    [array[i], array[j]] = [array[j], array[i]];
  }
}

Hãy để thử nghiệm nó theo cùng một cách:

const getShuffledArr = arr => {
    const newArr = arr.slice()
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr
};

0

Ví dụ đầu ra:

const getShuffledArr = arr => {
    const newArr = arr.slice()
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr
};

1

Bây giờ có vẻ tốt: Tất cả các hoán vị xuất hiện với cùng một xác suất.

Ngoài ra, thuật toán Fisher-Yates khôn ngoan hơn nhiều, ở đó, không có sự sắp xếp nào trên đầu.

Làm thế nào để bạn xáo trộn các mục trong JavaScript?

Làm thế nào để bạn xáo trộn một chuỗi trong javascript?

Làm thế nào để bạn ngẫu nhiên một mảng trong javascript?

Bạn có thể xáo trộn một mảng không?