Míchání pole

Napište funkci zamíchej(pole), která zamíchá (náhodně seřadí) prvky pole.

Vícenásobná volání zamíchej mohou vést k různým pořadím prvků. Například:

          let pole = [1, 2, 3];

zamíchej(pole);
// pole = [3, 2, 1]

zamíchej(pole);
// pole = [2, 1, 3]

zamíchej(pole);
// pole = [3, 1, 2]
// ...
        

Všechna pořadí prvků by měla mít stejnou pravděpodobnost. Například [1,2,3] lze seřadit jako [1,2,3] nebo [1,3,2] nebo [3,1,2] atd., přičemž všechny možnosti mají mít stejnou pravděpodobnost.

Jednoduché řešení by mohlo být:

function zamíchej(pole) {
  pole.sort(() => Math.random() - 0.5);
}

let pole = [1, 2, 3];
zamíchej(pole);
alert(pole);

To jakžtakž funguje, protože Math.random() - 0.5 je náhodné číslo, které může být kladné nebo záporné, takže řadicí funkce přehází prvky náhodně.

Protože však řadicí funkce není určena k takovému použití, nebudou mít všechny permutace stejnou pravděpodobnost.

Například uvažujte níže uvedený kód. Spustí zamíchej 1 000 000krát a spočítá výskyty všech možných výsledků:

function zamíchej(pole) {
  pole.sort(() => Math.random() - 0.5);
}

// spočítáme výskyty všech možných permutací
let počty = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let pole = [1, 2, 3];
  zamíchej(pole);
  počty[pole.join('')]++;
}

// zobrazíme počty všech možných permutací
for (let klíč in počty) {
  alert(`${klíč}: ${počty[klíč]}`);
}

Příklad výsledku (závisí na motoru JavaScriptu):

          123: 250706
124425
249618
124880
125148
125223
        

Jasně vidíme odchylku: 123 a 213 se objevují mnohem častěji než ostatní.

Výsledek kódu se může u různých JavaScriptových motorů lišit, ale už vidíme, že tento přístup je nespolehlivý.

Proč to nefunguje? Zhruba řečeno, sort je „černá skříňka“: vhodíme do ní pole a porovnávací funkci a očekáváme, že pole bude seřazeno. Kvůli naprosté náhodnosti řazení se však černá skříňka zblázní. To, jak přesně se zblázní, závisí na konkrétní implementaci, která se mezi jednotlivými motory liší.

Existují jiné dobré způsoby, jak tuto úlohu vyřešit. Například existuje skvělý algoritmus nazvaný Fisher-Yatesovo míchání. Myšlenkou je procházet pole v obráceném pořadí a vyměnit každý prvek s jiným prvkem před ním, náhodně vybraným:

          function zamíchej(pole) {
  for (let i = pole.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1)); // náhodný index od 0 do i

    // vyměníme prvky pole[i] a pole[j]
    // dosáhneme toho použitím syntaxe „destrukturačního přiřazení“
    // podrobnosti o této syntaxi najdete v dalších kapitolách
    // totéž lze zapsat jako:
    // let t = pole[i]; pole[i] = pole[j]; pole[j] = t
    [pole[i], pole[j]] = [pole[j], pole[i]];
  }
}
        

Otestujme to stejným způsobem:

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

// spočítáme výskyty všech možných permutací
let počty = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let pole = [1, 2, 3];
  zamíchej(pole);
  počty[pole.join('')]++;
}

// zobrazíme počty všech možných permutací
for (let klíč in počty) {
  alert(`${klíč}: ${počty[klíč]}`);
}

Příklad výstupu:

          123: 166693
166647
166628
167517
166199
166316
        

Nyní to vypadá dobře: všechny permutace se objevují se stejnou pravděpodobností.

Navíc je Fisher-Yatesův algoritmus mnohem méně náročný na výkon, jelikož v něm není žádné „řazení“.