آرایه را بُر بزنید

تابع shuffle(array) را بنویسید که المان‌های آرایه را بُر می‌زند (به طور تصادفی ترتیب‌بندی می‌کند).

هر بار فراخوانی shuffle ممکن است به ترتیب متفاوتی از المان‌ها منجر شود. برای مثال:

          let arr = [1, 2, 3];

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

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

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

ترتیب تمام المان‌ها باید احتمال برابر داشته باشند. برای مثال، [1,2,3] می‌تواند به شکل [1,2,3] یا [1,3,2] یا [3,1,2] و… مرتب شود که احتمال هر مورد برابر است.

راه حل ساده می‌تواند اینگونه باشد:

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

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

این کد تا حدی کار می‌کند، چون Math.random() - 0.5 یک عدد تصادفی است که ممکن است مثبت یا منفی باشد، پس تابع مرتب‌کننده المان‌ها را به صورت تصادفی مرتب می‌کند.

اما به دلیل اینکه تابع مرتب‌کننده قرار نیست اینگونه استفاده شود، تمام جابجایی‌ها احتمال برابر ندارند.

برای مثال، کد زیر را در نظر بگیرید. این کد shuffle را 1000000 بار اجرا می‌کند و تعداد وقوع تمام نتایج ممکن را می‌شمارد:

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

// شمارش تعداد وقوع تمام جایجایی‌های ممکن
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('')]++;
}

// نمایش شمارش تمام جابجایی‌های ممکن
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

نتیجه یک مثال (با وابستگی به موتور جاوااسکریپت):

          123: 250706
124425
249618
124880
125148
125223
        

می‌توانیم جانب‌داری را به طور واضح ببینیم: 123 و 213 نسبت به بقیه بیشتر رخ می‌دهند.

نتیجه کد ممکن است بین موتورهای جاوااسکریپت متفاوت باشد، اما می‌توانیم به سادگی ببینیم که این شیوه قابل اطمینان نیست.

چرا درست کار نمی‌کند؟ به طور کلی، sort یک «جعبه سیاه» است: ما یک آرایه و تابع مقایسه را درون آن می‌اندازیم و توقع داریم که آرایه مرتب شود. اما به دلیل منطق تصادفی مقایسه، جعبه سیاه دیوانه می‌شود و اینکه چگونه دیوانه می‌شود بستگی به پیاده‌سازی دارد که بین موتورها متفاوت است.

راه‌های خوب دیگری هم برای انجام تکلیف وجود دارد. برای مثال، یک الگوریتم عالی به اسم بُرزدن Fisher-Yates وجود دارد. ایده اینگونه است که آرایه را برعکس بررسی کنیم و هر المان را با یک المان تصادفی قبل خود جابجا کنیم:

          function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1)); // i ایندکس تصادفی بین 0 تا

    // را جابجا کن array[j] و array[i] المان‌های
    // ما از سینتکس «مقداردهی تخریب‌ساختار» برای انجام آن استفاده می‌کنیم
    // شما درباره سینتکس آن در فصل‌های آینده بیشتر یاد می‌گیرید
    // به طور یکسان می‌توان نوشت:
    // let t = array[i]; array[i] = array[j]; array[j] = t
    [array[i], array[j]] = [array[j], array[i]];
  }
}
        

بیایید مانند قبل آن را آزمایش کنیم:

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]];
  }
}

// شمارش تعداد وقوع تمام جایجایی‌های ممکن
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('')]++;
}

// نمایش شمارش تمام جابجایی‌های ممکن
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

خروجی نمونه:

          123: 166693
166647
166628
167517
166199
166316
        

الان بنظر خوب می‌آید: تمام جایجایی‌ها با احتمال یکسان رخ می‌دهند.

همچنین، الگوریتم Fisher-Yates که از نظر عملکرد بهینه می‌باشد، بسیار بهتر است، و هیچ مرتب‌سازی‌ای بر روی آن وجود ندارد.