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

Перейти к навигации Перейти к поиску
Переработана реализация на 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> переставить в обратном порядке.
 
=Реализации=
</source>
 
'''C++:''' ОбеВсе функции, кроме main, следует предварить строкой:
<source lang="cpp">
template < typename T >
Собственно реализация:
<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 *sequence, intunsigned const count, int (*compare)(T const, T const)) {
int i, j, l;
unsigned i = count, j;
/* Этап № 1 */
++j;do {
for (j = count - 2; j >= 0 && sequence[j] >= sequence[j + 1]; --j);
if (ji ==< -12)
return 0;
int i, j, l --i;
} while (!(*compare)(sequence[i - 1], sequence[i]));
/* Этап № 2 */
for (j = count - 2; j >= 0i && !(*compare)(sequence[ji - 1] >=, sequence[j +- 1]); --j);
if (j == -1)
return 0--i;
swapItems(sequence, li, j - 1);
for (l = count - 1; sequence[j] >= sequence[l]; --l);
swapItems(sequence, l, j);
++j;
/* Этап № 3 */
for (ij = 0i + 1; ij <= (count - j + 1i) >> 1; ++ij) /* >> 1 — более быстрый вариант / 2 */
swapItems(sequence, j + i, count -+ i - 1j);
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>
TPredicate2 = function (const value_0, value_1: T): Boolean;
 
{ Поиск очередной перестановки }
function NextPermutation (var sequence: array of T; Compare: TPredicate2): Word;
var count, i, j: Word;
i := count;
repeat
if i <= 12 then
begin
NextPermutation := 0;
74

правки

Навигация