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

Добавлена реализация и пример её использования на основе C++11
(Добавлена реализация и пример использования на Rust; мелкие правки для остальных языков)
(Добавлена реализация и пример её использования на основе C++11)
Если не оговорено другое, то функция поиска очередной перестановки возвращает ненулевое значение, если перестановка найдена, либо 0, если следующей перестановки не существует (перебор закончен).
 
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]==
'''C:''' Тип <code>T</code> должен быть предварительно определён как:
<source lang="cpp">
/* narayana.h */
typedef int T; /* Вместо int можно подставить любой тип */
</source>
 
'''C++:''' Все функции, кроме <code>main</code>, следует предварить строкой:
<source lang="cpp">
template < typename T >
</source>
 
Собственно реализация:
<source lang="cpp">
/* narayana.h */
/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2);
 
 
/* narayana.c или narayana.cpp */
/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2) {
Пример использования:
<source lang="cpp">
/* narayana_test.c или narayana_test.cpp */
#include <malloc.h>
#include <stdio.h>
T *sequence = (T*)malloc(count * sizeof(T));
/* Для C++ заменить в предыдущей строке все T на int или любой другой тип, для которого определены операции < и > */
initSequence(sequence, count); /* Формирование исходной последовательности */
printf("Неубывающая последовательность и её перестановки:\n");
} 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;
}
Анонимный участник