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

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

procedure TDSimpleListShuffie(aList : TList;
aStart, aEnd : integer);
var
Range : integer;
Inx : integer;
Randomlnx : integer;
TempPtr : pointer;
begin
TDValidateListRange(aList, aStart, aEnd, 'TDSimpleListShuffle');
Range := succ(aEnd - aStart) ; for Inx : = aStart to aEnd do begin
Randomlnx := aStart + Random (Range) ;
TempPtr := aList.ListA[Inx];
aList.ListA[Inx] : = aList.ListA[Randomlnx];
aList.ListA[Randomlnx] : = TempPtr;
end;
end;

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

С описанным алгоритмом связана только одна проблема. Если рассматривать тасование с другой точки зрения, с позиции главных принципов, можно показать, что для первой позиции можно выбрать один из п элементов. После этого для второй позиции останется выбор только из п - 1 элементов. Далее для третьей позиции элементов будет уже п - 2 и т.д. В результате таких рассуждений можно прийти к выводу, что общее количество возможных комбинаций будет вычисляться как п\ (п\ означает п факториал и сводится к произведению п * (п- 1) * (п-2) *...* 1.) Вернемся к проблеме: если не брать во внимание случай, когда п = 1, пп больше, а часто намного больше, чем п\ Таким образом, с помощью описанного алгоритма формируются повторяющиеся последовательности, причем некоторые из них будут повторяться чаще, нежели другие, поскольку пп не делится на п\ без остатка.

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

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

procedure TDLi st Shuffle (aList : TList;
aStart, aEnd : integer); var
Range : integer;
Inx : integer;
Randomlnx : integer;
TempPtr : pointer;
begin
TDValidateListRange(abist, aStart, aEnd, 1TDListShuffle');
{для каждого элемента, считая справа...}
for Inx := (aEnd - aStart) downto aStart + 1 do begin
{сгенерировать случайное число из диапазона от aStart до текущего индекса}
Randomlnx := aStart + Random(Inx-aStart+l);
{если случайный индекс не равен текущему, переставить элементы} if (Randomlnxoinx) then begin TempPtr : = aList.ListA[Inx]; aList.ListA[Inx] : - aList.ListA[Randomlnx]; aList.ListA [Randomlnx] TempPtr;
end;
end;
end;

Алгоритмы сортировки || Оглавление || Основы сортировки


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



Новости за месяц

  • Июль
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс