Massivni aralashtirish

Massiv elementlarini aralashtiruvchi (tasodifiy tartiblash) shuffle(array) funktsiyasini yozing.

Bir necha marta aralashtirish elementlarning turli xil tartiblariga olib kelishi mumkin. Misol uchun:

          let arr = [1, 2, 3];

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

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

shuffle(arr);
// arr = [3, 1, 2]
// ...
        

Barcha element chaqiruvlari teng ehtimolga ega bo’lishi kerak. Masalan, [1,2,3] teng ehtimollik bilan [1,2,3] yoki [1,3,2] yoki [3,1,2] va boshqalar sifatida o’zgartirilishi mumkin.

Oddiy yechim bo’lishi mumkin:

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

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

Bu biroz ishlaydi, chunki Math.random() - 0.5 tasodifiy son bo’lib, u ijobiy yoki salbiy bo’lishi mumkin, shuning uchun saralash funktsiyasi elementlarni tasodifiy tartibda o’zgartiradi.

Ammo saralash funktsiyasi shu tarzda ishlatilishi mumkin emasligi sababli, barcha almashtirishlar bir xil ehtimollikka ega emas.

Masalan, quyidagi kodni ko’rib chiqing. U aralashtirib 1000000 marta ishlaydi va barcha mumkin bo’lgan natijalarning ko’rinishini hisoblaydi:

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

// barcha mumkin bo'lgan almashtirishlar uchun ko'rinishlarning soni
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("")]++;
}

// barcha mumkin bo'lgan almashtirishlarning sonlarini ko'rsatish
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

Misol natijasi (for V8, July 2017):

          123: 250706
124425
249618
124880
125148
125223
        

Ikkilanishni aniq ko’rishimiz mumkin: 123 va 213 boshqalarga qaraganda tez-tez ko’rinadi.

Kod natijasi JavaScript interpretator o’rtasida farq qilishi mumkin, ammo biz allaqachon yondashuv ishonchsizligini ko’rmoqdamiz.

Nima uchun u ishlamayapti? Umuman aytganda, sort “qora quti” dir: biz unga qator va taqqoslash funktsiyasini tashlaymiz va massivning tartiblanishini kutamiz. Ammo taqqoslashning mutlaqo tasodifiyligi tufayli qora quti aqldan ozadi va uning aynan qay darajada aqldan ozishi interpretator orasidagi farqning aniq bajarilishiga bog’liq.

Vazifani bajarishning boshqa yaxshi usullari mavjud. Masalan, Fisher-Yates shuffle deb nomlangan ajoyib algoritm mavjud. Maqsad massivni teskari tartibda o’tkazosh va har bir elementni tasodifiy element bilan almashtirishdir:

          function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1)); // 0 dan i gacha bo'lgan tasodifiy indeks
    [array[i], array[j]] = [array[j], array[i]]; // elementlarni almashtirish
  }
}
        

Keling, xuddi shu tarzda sinab ko’raylik:

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

// barcha mumkin bo'lgan almashtirishlar uchun ko'rinishlarning soni
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("")]++;
}

// barcha mumkin bo'lgan almashtirishlarning sonlarini ko'rsatish
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

Misol natijasi:

          123: 166693
166647
166628
167517
166199
166316
        

Hozir yaxshi ko’rinishga ega: barcha almashtirishlar bir xil ehtimollik bilan paydo bo’ladi.

Shuningdek, Fisher-Yates algoritmi ishlash samaradorligi jihatidan ancha yaxshi, ortiqcha “saralash” mavjud emas.