Тасування масиву TList

тасування

Книга "Фундаментальні алгоритми та структури даних у Delphi" є унікальним навчальним та довідковим посібником за найбільш поширеними алгоритмами маніпулювання даними, які зарекомендували себе як надійні та перевірені багатьма поколіннями програмістів. За даними журналу Delphi Informant за 2002 рік, ця книга була визнана спільнотою розробників прикладних додатків на Delphi як «найкраща книга з практичного застосування всіх версій Delphi».

У книзі докладно розглядаються базові поняття алгоритмів та основні структури даних, алгоритми сортування, пошуку, хешування, синтаксичного розбору, стиснення даних, а також багато інших тем, тісно пов'язані з прикладним програмуванням. Достаток ретельно перевірених прикладів коду суттєво прискорює не тільки освоєння фундаментальних алгоритмів, але також сприяє більш кваліфікованому підходу до повсякденного програмування.

Незважаючи на те, що книга розрахована в першу чергу на професійних розробників додатків на Delphi, вона виявить безсумнівну користь і програмістам-початківцям, демонструючи їм прийоми і трюки, які настільки популярні у справжніх «профі». Усі коди прикладів, згадані у книзі, доступні для вивантаження на веб-сайті видавництва.

Фундаментальні алгоритми та структури даних у Delphi

Тасування масиву TList

Тасування масиву TList

Як можна перетасувати елементи масиву TList? Більшість із вас як перший алгоритм приведуть найпростіший: відвідати кожен елемент масиву, від першого до останнього, і переставити його з іншим, випадково вибраним елементом. Реалізація такого алгоритму в Delphi буде виглядати так:

Лістинг 5.2. Простетасування елементів

procedure TDSimpleListShuffie(aList : TList;

aStart, aEnd: integer);

TDValidateListRange(aList, aStart, aEnd, 'TDSimpleListShuffle');

Range: = succ (aEnd - aStart);

for Inx := aStart to aEnd do

Randomlnx: = aStart + Random (Range);

А тепер спробуємо визначити, скільки послідовностей можна отримати за допомогою наведеного алгоритму. Після першого виконання циклу ми отримаємо одну з n можливих комбінацій (перший елемент може бути переставлений з будь-яким іншим, включаючи себе). Після другого виконання циклу ми знову отримаємо одну з n можливих комбінацій, які разом із n комбінаціями після першого виконання дадуть n(^2^) можливих комбінацій. Очевидно, що після виконання циклу ми отримаємо одну з n(^n^) можливих комбінацій.

З описаним алгоритмом пов'язана лише одна проблема. Якщо розглядати тасування з іншого погляду, з позиції основних принципів, можна показати, що з першої позиції можна вибрати одне із n елементів. Після цього другої позиції залишиться вибір лише з n - 1 елементів. Далі для третьої позиції елементів буде вже n – 2 і т.д. В результаті таких міркувань можна дійти висновку, що загальна кількість можливих комбінацій обчислюватиметься як n! (n! означає n факторіал і зводиться до твору n*(n-1)*(n-2)*.*1.)

Повернемося до проблеми: якщо не брати до уваги випадок, коли n = 1, n(^n^) більше, а часто набагато більше, ніж n! Таким чином, за допомогою описаного алгоритму формуються послідовності, що повторюються, причому деякі з них будуть повторюватися частіше, ніж інші, оскільки n(^n^) не ділиться на n! без залишку.

Як більш ефективний алгоритм тасування можна запропонувати метод, здопомогою якого ми визначили точну кількість можливих комбінацій: брати перший елемент з усіх n елементів, другий - з елементів, що залишилися (n - 1) і т.д. На основі такого алгоритму можна створити наступну реалізацію, де для зручності обчислення індексу цикл починається з кінця, а не початку масиву.

Лістинг 5.3. Коректний метод тасування масиву TList

procedure TDListShuffle(aList : TList; aStart, aEnd : integer);

TDValidateListRange(aList, aStart, aEnd, 'TDListShuffle');