Реализации алгоритмов/Алгоритм Нарайаны

Алгори́тм Нарайа́ны — нерекурсивный алгоритм, генерирующий по данной перестановке следующую за ней в лексикографическом порядке перестановку.

Алгоритм

Пусть $sequence$ — последовательность из $count$ элементов, для которых требуется найти очередную в лексикографическом порядке перестановку.

Алгоритм поиска очередной перестановки для последовательности с неубывающим (невозрастающим) изначальным порядком элементов:

1. Найти наибольшее $i$, для которого выполняется условие $sequence_{i}<sequence_{i+1}$ ($sequence_{i}>sequence_{i+1}$). Если такого нет, значит все перестановки были сгенерированы.
2. Найти наибольшее $j$, для которого выполняется условие $sequence_{i}<sequence_{j}$ ($sequence_{i}>sequence_{j}$). Затем поменять местами $sequence_{i}$ и $sequence_{j}$.
3. Записать последовательность $sequence_{i+1},...,sequence_{count}$ в обратном порядке.

Реализации

В нижеприведённых реализациях sequence — последовательность из count элементов, в которой производятся перестановки (как правило — массив из count элементов), compare(x, y) — функция, которая должна возвращать true если x < y и false иначе (если исходный порядок элементов последовательности неубывающий; для невозрастающего исходного порядка условие меняется на x > y).

Если не оговорено другое, то функция поиска очередной перестановки возвращает ненулевое значение, если перестановка найдена, либо 0, если следующей перестановки не существует (перебор закончен).

C/C++

C: Тип T должен быть предварительно определён как:

typedef int T; /* Вместо int можно подставить любой тип */

C++: Обе функции следует предварить строкой:

template < typename T >

Собственно реализация:

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 *sequence, int const count) {
    int i, j, l;
    /* Этап № 1 */
    for (j = count - 2; j >= 0 && sequence[j] >= sequence[j + 1]; --j);
    /* Этап № 2 */
    if (j == -1)
        return 0;
    for (l = count - 1; sequence[j] >= sequence[l]; --l);
    swapItems(sequence, l, j);
    ++j;
    /* Этап № 3 */
    for (i = 0; i < (count - j + 1) >> 1; ++i)
		swapItems(sequence, j + i, count - i - 1);
    return j;
}

Pascal

type T = Integer; { Вместо Integer можно использовать любой тип }
     { Функция, задающая отношение порядка для значений типа T (< либо >) }
     TPredicate2 = function (const value_0, value_1: T): Boolean;

function NextPermutation (var sequence: array of T; Compare: TPredicate2): Word;
var count, i, j: Word;
    { Обмен значениями двух элементов последовательности }
    procedure SwapItems (index_1, index_2: Word);
    var _: T; { _ — временная переменная }
    begin
        _ := sequence[index_1];
        sequence[index_1] := sequence[index_2];
        sequence[index_2] := _
    end;
begin
    count := Length(sequence);
    { Этап № 1 }
    i := count;
    repeat
        if i <= 1 then
        begin
            NextPermutation := 0;
            Exit
        end;
        i := i - 1
    until Compare(sequence[i - 1], sequence[i]);
    { Этап № 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;

Пример использования:

{ Возвращает 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.

PHP

Вариант № 1

function nextPermutation ($sequence, $count) {
    $out = $sequence;
    // Этап № 1
    $k = $count - 2;
    while ($k >= 0 && $out[$k] >= $out[$k + 1]) {
	    --$k;
    }
    if (-1 == $k) {
	    return false;
    }
    // Этап № 2
    $t = $count - 1;
    while ($t >= 0 && $t >= $k + 1 && $out[$k] >= $out[$t]) {
	    --$t;
    }
    $tmp = $out[$k];
    $out[$k] = $out[$t];
    $out[$t] = $tmp;
    // Этап № 3
    for ($i = $k + 1; $i < ceil(($count + $k) / 2); ++$i) {
	    $t = $count + $k - $i;
	    $tmp = $out[$i];
	    $out[$i] = $out[$t];
	    $out[$t] = $tmp;
    }

    return $out;
}

Вариант № 2

Вариант с выводом справа налево:

$b = "123456789";
$a = strrev($b);
while ($a !=$b) {
    $i = 0;

    while($a[$i] > $a[$i - 1]) {
        $i++;
    }
    $j = 0;
    while($a[$j] < $a[$i]) {
        ++$j;
    }

    $c = $a[$j];
    $a[$j] = $a[$i];
    $a[$i] = $c;

    $x = strrev(substr($a, 0, $i));
    $y = substr($a, $i);

    print $a = $x . $y;
    print ‘<br/>’;
}