Алгоритм перемішування масиву
У черговий раз зустрілося просте, але цікаве завдання – у заданому масиві перемішати наявні значення.
Іноді це завдання формулюється як заповнення масиву неповторними значеннями у випадковому порядку. Але писати алгоритм, який буде генерувати випадкове число, потім перевіряти, чи це значення не повториться з вже заповненими елементами, нераціонально. Набагато правильніше просто перемішати заданий масив. Тим більше, що це дозволить не ускладнювати процес підбору допустимих значень, дотримуючись унікальності кожного значення або враховуючи входження кожного значення задану кількість разів.
У результаті, завдання зводиться лише до перемішування наявної послідовності незалежно від її вихідного складу та впорядкованості.
Найпростіше рішення було б у циклі виконати N операцій заміни двох елементів, індекси яких вибираються випадково. Величина N визначає якість такого перемішування – чим більше замін, тим якісніший результат. Недолік цього методу полягає в тому, що деякі елементи масиву (особливо якщо він великий) можуть залишитися на своїх вихідних місцях. Також недолік буде можливість багаторазового переміщення одного і того ж елемента масиву. У результаті, нераціональне збільшення кількості замін, все ж таки не веде до 100% якісної перетасовки всіх елементів.
Більш якісний і в плані переміщення всіх елементів, і в кількості операцій перемішування:
- Вибираємо випадковий елемент масиву;
- Змінюємо його місцями з останнім елементом;
- Знову вибираємо випадковий елемент масиву, не торкаючись останній;
- Змінюємо з передостаннім;
Таким чином, вибираємо зі списку, що звужуєтьсявипадковий елемент та ставимо останнім у цьому списку. Для переміщення всіх елементів потрібно одне переміщення менше, ніж кількість елементів у масиві.
const N = 9; // розмір масиву var mas: array [1.. N] of Integer; i, r, h: Integer; begin Randomize; for i := N downto 2 do begin r := Random(i) + 1; // Вибір випадкового елемента
if r <> i then begin // заміна елементів h := mas[i]; mas[i]: = mas[r]; mas[r]: = h; end; end; end;
У цьому рішенні існує ймовірність випадання як випадковий елемент того, на який проводиться заміна. Щоб уникнути безглуздого переміщення одного елемента, є перевірка, яка виключить зайву заміну. Однак, у такому разі, є ймовірність, що деякі елементи масиву можуть залишитись на своєму місці.
Щоб виключити цей недолік, можна робити вибірку випадкового значення, не торкаючись крайнього елемента, що замінюється. Так як заздалегідь відомо, що елемент, що замінюється, обраний бути не може, додаткова умова тут не потрібно.
const N = 9; // розмір масиву var mas: array [1.. N] of Integer; i, r, h: Integer; begin Randomize; for i := N downto 2 do begin r := Random(i-1) + 1; // Вибір випадкового елемента
// Заміна елементів h := mas[i]; mas[i]: = mas[r]; mas[r]: = h; end; end;
Застосування такого алгоритму гарантує, що жоден елемент не залишиться на колишньому місці.