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

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

Во всех приведенных ниже реализациях a — массив, в котором в прямом порядке записана перестановка, а n — количество элементов в перестановке.

C

typedef int T;

void swapItems (T *array, unsigned index_1, unsigned index_2) {
    T temp = array[index_1];
    array[index_1] = array[index_2];
    array[index_2] = temp;
}

int NarayanaNextPermutation (T *a, int n) {
    int i, j, l;
    /* Шаг № 1 */
    for (j = n - 2; j >= 0 && a[j] >= a[j + 1]; --j);
    /* Шаг № 2 */
    if (j == -1)
        return 0;
    for (l = n - 1; a[j] >= a[l]; --l);
    swapItems(a, l, j);
    ++j;
    /* Шаг № 3 */
    for (i = 0; i < (n - j + 1) >> 1; ++i)
		swapItems(a, j + i, n - i - 1);
    return j;
}

Pascal

type T = integer;

function NarayanaNextPermutation (var a: array of T; n: integer): integer;
var i, k, l: integer;
    procedure SwapItems (index_1, index_2: word);
    var temp: T;
    begin
        temp := a[index_1];
        a[index_1] := a[index_2];
        a[index_2] := temp
    end;
begin
    { Шаг № 1 }
    k := n - 2;
    while (k >= 0) and (a[k] >= a[k + 1]) do
        k := k - 1;
    if k = -1 then
        NarayanaNextPermutation := 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
            l := n + k - i;
            SwapItems(i, l)
        end;
        NarayanaNextPermutation := i
    end
end;

PHP

Вариант № 1

function NarayanaNextPermutation ($a, $n) {
    $out = $a;
    // Шаг № 1
    $k = $n - 2;
    while ($k >= 0 && $out[$k] >= $out[$k + 1]) {
	    --$k;
    }
    if (-1 == $k) {
	    return false;
    }
    // Шаг № 2
    $t = $n - 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(($n + $k) / 2); ++$i) {
	    $t = $n + $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/>’;
}