Реализации алгоритмов/Алгоритм Нарайаны: различия между версиями
Содержимое удалено Содержимое добавлено
Добавлена реализация и пример использования на Rust; мелкие правки для остальных языков |
Добавлена реализация и пример её использования на основе C++11 |
||
Строка 15:
Если не оговорено другое, то функция поиска очередной перестановки возвращает ненулевое значение, если перестановка найдена, либо 0, если следующей перестановки не существует (перебор закончен).
==[[w:C (язык программирования)|C
<source lang="cpp">
/* narayana.h */▼
typedef int T; /* Вместо int можно подставить любой тип */
</source>▼
<source lang="cpp">▼
template < typename T >▼
</source>▼
<source lang="cpp">▼
▲/* narayana.h */
/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2);
Строка 35 ⟶ 26 :
/* narayana.c
/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2) {
Строка 63 ⟶ 54 :
Пример использования:
<source lang="cpp">
/* narayana_test.c
#include <malloc.h>
#include <stdio.h>
Строка 103 ⟶ 94 :
T *sequence = (T*)malloc(count * sizeof(T));
initSequence(sequence, count); /* Формирование исходной последовательности */
printf("Неубывающая последовательность и её перестановки:\n");
Строка 115 ⟶ 105 :
} while (nextPermutation(sequence, count, &greater)); /* x > y — критерий сравнения для невозрастающей последовательности */
free(sequence);
return 0;
}
▲</source>
==[[w:C++|C++]]==
Для C++11 или более позднего стандарта. На основе итераторов.
▲<source lang="cpp">
// narayana.hpp
namespace Narayana {
// Обмен значениями двух элементов последовательности
template < typename Iterator >
static void _swapItems (Iterator iterator_1, Iterator iterator_2) {
auto _ = *iterator_1; // _ — временная переменная
*iterator_1 = *iterator_2;
*iterator_2 = _;
}
// Поиск очередной перестановки
template < typename Iterator, typename T >
bool nextPermutation (Iterator const begin, Iterator const end, bool (*compare)(T const, T const)) {
if (begin == end) // Если последовательность не содержит элементов
return false;
// Этап № 1
Iterator i = end - 1, j = end;
do {
if (i == begin)
return false;
} while (!(*compare)(*--i, *--j));
// Этап № 2
j = end;
while (j != i && !(*compare)(*i, *--j));
_swapItems(i, j);
// Этап № 3
++i;
j = end;
for ( ; (i != j) && (i != --j); ++i)
_swapItems(i, j);
return true;
}
}
▲</source>
Пример использования:
▲<source lang="cpp">
// narayana_test.cpp
#include <iostream>
#include "narayana.hpp"
▲template < typename T >
bool less (T value_0, T value_1) {
return value_0 < value_1;
}
template < typename Iterator >
void outputSequence (Iterator const begin, Iterator const end) {
std::cout << '[';
if (begin != end) {
std::cout << *begin;
for (auto current = begin; ++current != end; )
((std::cout << ',') << ' ') << *current;
}
(std::cout << ']') << '\n';
}
template < typename Iterator >
void initSequence (Iterator const begin, Iterator const end) {
int i = 0;
for (Iterator current = begin; current != end; ++current)
*current = ++i;
}
int main () {
unsigned count;
std::cin >> count;
int *sequence = new int[count], *sequence_end = sequence + count;
initSequence(sequence, sequence_end);
do {
outputSequence(sequence, sequence_end);
} while (Narayana::nextPermutation(sequence, sequence_end, &less<int>));
delete [] sequence;
return 0;
}
| |||