Викиучебник

Реализации алгоритмов/Алгоритм Нарайаны: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
Добавлено описание алгоритма; усовершенствована реализация на Pascal, добавлен пример использования
Строка 2:
'''Алгори́тм Нарайа́ны''' — нерекурсивный алгоритм, генерирующий по данной [[w:Перестановка|перестановке]] следующую за ней в [[w:Лексикографический порядок|лексикографическом порядке]] перестановку.
 
=Алгоритм=
Во всех приведенных ниже реализациях <code>a</code> — массив, в котором в прямом порядке записана перестановка, а <code>n</code> — количество элементов в перестановке.
Пусть <math>sequence</math> — последовательность из <math>count</math> элементов, для которых требуется найти очередную в лексикографическом порядке перестановку.
 
Алгоритм поиска очередной перестановки для последовательности с неубывающим (невозрастающим) '''изначальным''' порядком элементов:
==[[w:C (язык программирования)|C]]==
# Найти наибольшее <math>i</math>, для которого выполняется условие <math>sequence_{i} < sequence_{i+1}</math> (<math>sequence_{i} > sequence_{i+1}</math>). Если такого нет, значит все перестановки были сгенерированы.
# Найти наибольшее <math>j</math>, для которого выполняется условие <math>sequence_{i} < sequence_{j}</math> (<math>sequence_{i} > sequence_{j}</math>). Затем поменять местами <math>sequence_{i}</math> и <math>sequence_{j}</math>.
# Записать последовательность <math>sequence_{i+1},...,sequence_{count}</math> в обратном порядке.
 
=Реализации=
В нижеприведённых реализациях <code>sequence</code> — последовательность из <code>count</code> элементов, в которой производятся перестановки (как правило — массив из count элементов), <code>compare(x, y)</code> — функция, которая должна возвращать <code>true</code> если x < y и <code>false</code> иначе (если исходный порядок элементов последовательности неубывающий; для невозрастающего исходного порядка условие меняется на x > y).
 
Если не оговорено другое, то функция поиска очередной перестановки возвращает ненулевое значение, если перестановка найдена, либо 0, если следующей перестановки не существует (перебор закончен).
 
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]==
'''C:''' Тип <code>T</code> должен быть предварительно определён как:
<source lang="cpp">
typedef int T; /* Вместо int можно подставить любой тип */
typedef int T;
</source>
 
'''C++:''' Обе функции следует предварить строкой:
void swapItems (T *array, unsigned index_1, unsigned index_2) {
<source lang="cpp">
T temp = array[index_1];
template < typename T >
array[index_1] = array[index_2];
</source>
array[index_2] = temp;
 
Собственно реализация:
<source lang="cpp">
void swapItems (T *sequence, unsigned index_1, unsigned index_2) {
T _ = sequence[index_1];
sequence[index_1] = sequence[index_2];
sequence[index_2] = _;
}
 
int nextPermutation (T *asequence, int nconst count) {
int i, j, l;
/* ШагЭтап № 1 */
for (j = ncount - 2; j >= 0 && asequence[j] >= asequence[j + 1]; --j);
/* ШагЭтап № 2 */
if (j == -1)
return 0;
for (l = ncount - 1; asequence[j] >= asequence[l]; --l);
swapItems(asequence, l, j);
++j;
/* ШагЭтап № 3 */
for (i = 0; i < (ncount - j + 1) >> 1; ++i)
swapItems(asequence, j + i, ncount - i - 1);
return j;
}
Строка 33 ⟶ 53 :
==[[w:Паскаль (язык программирования)|Pascal]]==
<source lang="pascal">
type T = Integer; { Вместо Integer можно использовать любой тип }
type T = integer;
{ Функция, задающая отношение порядка для значений типа T (< либо >) }
TPredicate2 = function (const value_0, value_1: T): Boolean;
 
function NextPermutation (var asequence: array of T; nCompare: integerTPredicate2): integerWord;
var icount, ki, lj: integerWord;
{ Обмен значениями двух элементов последовательности }
procedure SwapItems (index_1, index_2: word);
procedure SwapItems (index_1, index_2: Word);
var temp: T;
var _: T; { _ — временная переменная }
begin
temp_ := asequence[index_1];
asequence[index_1] := asequence[index_2];
asequence[index_2] := temp_
end;
begin
count := Length(sequence);
{ Шаг № 1 }
k{ :=Этап n№ -1 2;}
i := count;
while (k >= 0) and (a[k] >= a[k + 1]) do
k := k - 1;repeat
if ki <= -1 then
NextPermutation := 0
else
begin
{ Шаг № 2 }
l := n - 1;
while (l >= k + 1) and (a[k] >= a[l]) do
l := l - 1;
SwapItems(k, l);
{ Шаг № 3 }
for i := k + 1 to (n + k) div 2 do
begin
lNextPermutation := n + k - i0;
SwapItems(i, l)Exit
end;
NextPermutationi := i - 1
until Compare(sequence[i - 1], sequence[i]);
end
{ Этап № 2 }
j := count;
while (j > i) and not Compare(sequence[i - 1], sequence[j - 1]) do
j := j - 1;
i := i - 1;
SwapItems(i, j - 1);
{ Этап № 3 }
for j := i + 1 to (count + i) shr 1 do { shr 1 — более быстрый вариант div 2 }
SwapItems(j, count + i - j);
NextPermutation := j
end;
</source>
 
Пример использования:
<source lang="pascal">
{ Возвращает true, если value_0 меньше value_1, иначе — false }
function Less (const value_0, value_1: T): Boolean;
begin
Less := value_0 < value_1
end;
 
{ Возвращает true, если value_0 больше value_1, иначе — false }
function Greater (const value_0, value_1: T): Boolean;
begin
Greater := value_0 > value_1
end;
 
procedure InitSequence (var sequence: array of T);
var i: Word;
begin
{ Заполнение последовательности значениями 1, 2, 3… }
for i := Length(sequence) downTo 1 do
sequence[i - 1] := i;
end;
 
{ Выводит содержимое последовательности }
procedure OutputSequence (sequence: array of T);
var i, count: Word;
begin
Write('[');
count := Length(sequence);
if count > 0 then { Если последовательность не пуста }
begin
Write(sequence[0]);
for i := 1 to count - 1 do
Write(' ', sequence[i])
end;
WriteLn(']')
end;
 
BEGIN
InitSequence(sequence); { Формирование исходной последовательности }
WriteLn('Неубывающая последовательность и её перестановки:');
repeat
OutputSequence(sequence)
until NextPermutation(sequence, @Less) = 0; { x < y — критерий сравнения для неубывающей последовательности }
WriteLn;
WriteLn('Невозрастающая последовательность и её перестановки:');
repeat
OutputSequence(sequence)
until NextPermutation(sequence, @Greater) = 0 { x > y — критерий сравнения для невозрастающей последовательности }
END.
</source>
 
Строка 72 ⟶ 146 :
===Вариант № 1===
<source lang="PHP">
function nextPermutation ($asequence, $ncount) {
$out = $asequence;
// ШагЭтап № 1
$k = $ncount - 2;
while ($k >= 0 && $out[$k] >= $out[$k + 1]) {
--$k;
Строка 82 ⟶ 156 :
return false;
}
// ШагЭтап № 2
$t = $ncount - 1;
while ($t >= 0 && $t >= $k + 1 && $out[$k] >= $out[$t]) {
--$t;
Строка 90 ⟶ 164 :
$out[$k] = $out[$t];
$out[$t] = $tmp;
// ШагЭтап № 3
for ($i = $k + 1; $i < ceil(($ncount + $k) / 2); ++$i) {
$t = $ncount + $k - $i;
$tmp = $out[$i];
$out[$i] = $out[$t];
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Алгоритм_Нарайаны