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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Переработана реализация на C; добавлен пример использования
Строка 8: Строка 8:
# Найти наибольшее <math>i</math>, для которого выполняется условие <math>sequence_{i} < sequence_{i+1}</math> (<math>sequence_{i} > sequence_{i+1}</math>). Если такого нет, значит все перестановки были сгенерированы.
# Найти наибольшее <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>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> в обратном порядке.
# Элементы <math>sequence_{i+1}, ..., sequence_{count}</math> переставить в обратном порядке.


=Реализации=
=Реализации=
Строка 21: Строка 21:
</source>
</source>


'''C++:''' Обе функции следует предварить строкой:
'''C++:''' Все функции, кроме main, следует предварить строкой:
<source lang="cpp">
<source lang="cpp">
template < typename T >
template < typename T >
Строка 28: Строка 28:
Собственно реализация:
Собственно реализация:
<source lang="cpp">
<source lang="cpp">
/* Обмен значениями двух элементов последовательности */
void swapItems (T *sequence, unsigned index_1, unsigned index_2) {
void swapItems (T *sequence, unsigned index_1, unsigned index_2) {
T _ = sequence[index_1];
T _ = sequence[index_1]; /* _ — временная переменная */
sequence[index_1] = sequence[index_2];
sequence[index_1] = sequence[index_2];
sequence[index_2] = _;
sequence[index_2] = _;
}
}


/* Поиск очередной перестановки */
int nextPermutation (T *sequence, int const count) {
int nextPermutation (T *sequence, unsigned const count, int (*compare)(T const, T const)) {
int i, j, l;
unsigned i = count, j;
/* Этап № 1 */
/* Этап № 1 */
do {
for (j = count - 2; j >= 0 && sequence[j] >= sequence[j + 1]; --j);
if (i < 2)
return 0;
--i;
} while (!(*compare)(sequence[i - 1], sequence[i]));
/* Этап № 2 */
/* Этап № 2 */
for (j = count; j > i && !(*compare)(sequence[i - 1], sequence[j - 1]); --j);
if (j == -1)
return 0;
--i;
swapItems(sequence, i, j - 1);
for (l = count - 1; sequence[j] >= sequence[l]; --l);
swapItems(sequence, l, j);
++j;
/* Этап № 3 */
/* Этап № 3 */
for (i = 0; i < (count - j + 1) >> 1; ++i)
for (j = i + 1; j <= (count + i) >> 1; ++j) /* >> 1 — более быстрый вариант / 2 */
swapItems(sequence, j + i, count - i - 1);
swapItems(sequence, j, count + i - j);
return j;
return j;
}
</source>
Пример использования:
<source lang="cpp">
#include <malloc.h>
#include <stdio.h>


/* Возвращает 1, если value_0 меньше value_1, иначе — 0 */
int less (T const value_0, T const value_1) {
return value_0 < value_1;
}

/* Возвращает 1, если value_0 больше value_1, иначе — 0 */
int greater (T const value_0, T const value_1) {
return value_0 > value_1;
}

/* Инициализация последовательности */
void initSequence (T *sequence, unsigned count) {
/* Заполнение последовательности значениями 1, 2, 3… */
for (unsigned i = count; i; --i)
sequence[i - 1] = i;
}

/* Вывод содержимого последовательности */
void outputSequence (T const *sequence, unsigned count) {
putchar('[');
if (count) { /* Если последовательность не пуста */
printf("%d", sequence[0]);
for (unsigned i = 1; i < count; ++i)
printf(" %d", sequence[i]);
}
putchar(']');
putchar('\n');
}

int main () {
unsigned const count = 4; /* Длина последовательности. Может быть и любой другой */
T *sequence = (T*)malloc(count * sizeof(T));
/* Для C++ заменить в предыдущей строке все T на int или любой другой тип, для которого определены операции < и > */
initSequence(sequence, count); /* Формирование исходной последовательности */
printf("Неубывающая последовательность и её перестановки:\n");
do {
outputSequence(sequence, count);
} while (nextPermutation(sequence, count, &less)); /* x < y — критерий сравнения для неубывающей последовательности */
putchar('\n');
printf("Невозрастающая последовательность и её перестановки:\n");
do {
outputSequence(sequence, count);
} while (nextPermutation(sequence, count, &greater)); /* x > y — критерий сравнения для невозрастающей последовательности */
free(sequence);
return 0;
}
}
</source>
</source>
Строка 57: Строка 115:
TPredicate2 = function (const value_0, value_1: T): Boolean;
TPredicate2 = function (const value_0, value_1: T): Boolean;


{ Поиск очередной перестановки }
function NextPermutation (var sequence: array of T; Compare: TPredicate2): Word;
function NextPermutation (var sequence: array of T; Compare: TPredicate2): Word;
var count, i, j: Word;
var count, i, j: Word;
Строка 72: Строка 131:
i := count;
i := count;
repeat
repeat
if i <= 1 then
if i < 2 then
begin
begin
NextPermutation := 0;
NextPermutation := 0;

Версия от 22:27, 14 мая 2017

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

Алгоритм

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

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

  1. Найти наибольшее , для которого выполняется условие (). Если такого нет, значит все перестановки были сгенерированы.
  2. Найти наибольшее , для которого выполняется условие (). Затем поменять местами и .
  3. Элементы переставить в обратном порядке.

Реализации

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

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

C/C++

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

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

C++: Все функции, кроме main, следует предварить строкой:

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, unsigned const count, int (*compare)(T const, T const)) {
    unsigned i = count, j;
    /* Этап № 1 */
    do {
        if (i < 2)
            return 0;
        --i;
    } while (!(*compare)(sequence[i - 1], sequence[i]));
    /* Этап № 2 */
    for (j = count; j > i && !(*compare)(sequence[i - 1], sequence[j - 1]); --j);
    --i;
    swapItems(sequence, i, j - 1);
    /* Этап № 3 */
    for (j = i + 1; j <= (count + i) >> 1; ++j) /* >> 1 — более быстрый вариант / 2 */
		swapItems(sequence, j, count + i - j);
    return j;
}

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

#include <malloc.h>
#include <stdio.h>


/* Возвращает 1, если value_0 меньше value_1, иначе — 0 */
int less (T const value_0, T const value_1) {
    return value_0 < value_1;
}

/* Возвращает 1, если value_0 больше value_1, иначе — 0 */
int greater (T const value_0, T const value_1) {
    return value_0 > value_1;
}

/* Инициализация последовательности */
void initSequence (T *sequence, unsigned count) {
    /* Заполнение последовательности значениями 1, 2, 3… */
    for (unsigned i = count; i; --i)
        sequence[i - 1] = i;
}

/* Вывод содержимого последовательности */
void outputSequence (T const *sequence, unsigned count) {
    putchar('[');
    if (count) { /* Если последовательность не пуста */
        printf("%d", sequence[0]);
        for (unsigned i = 1; i < count; ++i)
            printf(" %d", sequence[i]);
    }
    putchar(']');
    putchar('\n');
}

int main () {
    unsigned const count = 4; /* Длина последовательности. Может быть и любой другой */
    
    T *sequence = (T*)malloc(count * sizeof(T));
    /* Для C++ заменить в предыдущей строке все T на int или любой другой тип, для которого определены операции < и > */
    initSequence(sequence, count); /* Формирование исходной последовательности */
    printf("Неубывающая последовательность и её перестановки:\n");
    do {
        outputSequence(sequence, count);
    } while (nextPermutation(sequence, count, &less)); /* x < y — критерий сравнения для неубывающей последовательности */
    putchar('\n');
    printf("Невозрастающая последовательность и её перестановки:\n");
    do {
        outputSequence(sequence, count);
    } while (nextPermutation(sequence, count, &greater)); /* x > y — критерий сравнения для невозрастающей последовательности */
    free(sequence);
    return 0;
}

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 < 2 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;

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

var sequence: array [0..3] of T; { Последовательность. Границы индексов могут быть и другими }

{ Возвращает 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 (const 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/>;
}