Реализации алгоритмов/Алгоритм Нарайаны: различия между версиями
Содержимое удалено Содержимое добавлено
м →Pascal |
Переработана реализация на C; добавлен пример использования |
||
Строка 8:
# Найти наибольшее <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>.
#
=Реализации=
Строка 21:
</source>
'''C++:'''
<source lang="cpp">
template < typename T >
Строка 28:
Собственно реализация:
<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,
int i, j, l;▼
unsigned i = count, j;
/* Этап № 1 */
for (j = count - 2; j >= 0 && sequence[j] >= sequence[j + 1]; --j);▼
return 0;
} while (!(*compare)(sequence[i - 1], sequence[i]));
/* Этап № 2 */
▲ if (j == -1)
▲ swapItems(sequence, l, j);
▲ ++j;
/* Этап № 3 */
for (
swapItems(sequence, 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>
Строка 57 ⟶ 115 :
TPredicate2 = function (const value_0, value_1: T): Boolean;
{ Поиск очередной перестановки }
function NextPermutation (var sequence: array of T; Compare: TPredicate2): Word;
var count, i, j: Word;
Строка 72 ⟶ 131 :
i := count;
repeat
if i <
begin
NextPermutation := 0;
| |||