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

Тасование массива TList

Тасование массива TList

Каким образом можно перетасовать элементы массива 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.List^[Inx];

aList.List^[Inx] := aList.List^[RandomInx];

aList.List^[RandomInx] := TempPtr;

end;

end;

А теперь давайте попробуем определить, сколько последовательностей можно получить с помощью приведенного алгоритма. После первого выполнения цикла мы получим одну из 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);

var

Range : integer;

Inx : integer;

RandomInx : integer;

TempPtr : pointer;

begin

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

{для каждого элемента, считая справа...}

for Inx := (aEnd - aStart) downto aStart + 1 do

begin

{сгенерировать случайное число из диапазона от aStart до текущего индекса}

RandomInx := aStart + Random(Inx-aStart+ 1);

{если случайный индекс не равен текущему, переставить элементы}

if (RandomInx <> Inx) then begin

TempPtr := aList.List^[Inx];

aList.List^[Inx] := aList.List^[RandomInx];

aList.List^ [RandomInx] TempPtr;

end;

end;

end;

Оглавление книги