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

Добавлена реализация и пример использования на Rust; мелкие правки для остальных языков
(Переработана реализация на C; добавлен пример использования)
(Добавлена реализация и пример использования на Rust; мелкие правки для остальных языков)
</source>
 
'''C++:''' Все функции, кроме <code>main</code>, следует предварить строкой:
<source lang="cpp">
template < typename T >
Собственно реализация:
<source lang="cpp">
/* narayana.h */
/* Обмен значениями двух элементов последовательности */
static void swapItems_swapItems (T *sequence, unsigned index_1, unsigned index_2) {;
/* Поиск очередной перестановки */
unsigned nextPermutation (T *sequence, unsigned const count, int (*compare)(T const, T const));
 
 
/* narayana.c или narayana.cpp */
/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2) {
T _ = sequence[index_1]; /* _ — временная переменная */
sequence[index_1] = sequence[index_2];
sequence[index_2] = _;
}
 
/* Поиск очередной перестановки */
intunsigned nextPermutation (T *sequence, unsigned const count, int (*compare)(T const, T const)) {
unsigned i = count, j;
/* Этап № 1 */
for (j = count; j > i && !(*compare)(sequence[i - 1], sequence[j - 1]); --j);
--i;
swapItems_swapItems(sequence, i, j - 1);
/* Этап № 3 */
for (j = i + 1; j <= (count + i) >> 1; ++j) /* >> 1 — более быстрый вариант / 2 */
swapItems_swapItems(sequence, j, count + i - j);
return j;
}
Пример использования:
<source lang="cpp">
/* narayana_test.c или narayana_test.cpp */
#include <malloc.h>
#include <stdio.h>
 
#include "narayana.h"
 
 
printf("%d", sequence[0]);
for (unsigned i = 1; i < count; ++i)
printf(", %d", sequence[i]);
}
putchar(']');
==[[w:Паскаль (язык программирования)|Pascal]]==
<source lang="pascal">
{ Narayana.pas }
type T = Integer; { Вместо Integer можно использовать любой тип }
UNIT Narayana;
{ Функция, задающая отношение порядка для значений типа T: < либо > }
TPredicate2 = function (const value_0, value_1: T): Boolean;
 
INTERFACE
{ Поиск очередной перестановки }
 
function NextPermutation (var sequence: array of T; Compare: TPredicate2): Word;
type T = Integer; { Вместо Integer можно использовать любой тип }
var count, i, j: Word;
{ Функция, задающая отношение порядка для значений типа T: < либо > }
{ Обмен значениями двух элементов последовательности }
TPredicate2 = function (const value_0, value_1: T): Boolean;
procedure SwapItems (index_1, index_2: Word);
 
var _: T; { _ — временная переменная }
{ Поиск очередной перестановки }
begin
function NextPermutation (var sequence: array of T; Compare: TPredicate2): Word;
_ := sequence[index_1];
 
sequence[index_1] := sequence[index_2];
IMPLEMENTATION
sequence[index_2] := _
 
end;
{ Поиск очередной перестановки }
begin
function NextPermutation (var sequence: array of T; Compare: TPredicate2): Word;
count := Length(sequence);
{var Этапcount, i, 1j: }Word;
{ Обмен значениями двух элементов последовательности }
i := count;
procedure SwapItems (index_1, index_2: Word);
repeat
var _: T; { _ — временная переменная }
if i < 2 then
begin
NextPermutation_ := 0sequence[index_1];
Exitsequence[index_1] := sequence[index_2];
sequence[index_2] := _
end;
i := i - 1begin
until Compare(sequence[i - 1], count := Length(sequence[i]);
{ Этап № 21 }
j i := count;
repeat
while (j > i) and not Compare(sequence[i - 1], sequence[j - 1]) do
j := j - 1;if i < 2 then
i := i - 1; begin
NextPermutation := 0;
SwapItems(i, j - 1);
{ Этап 3 } Exit
end;
for j := i + 1 to (count + i) shr 1 do { shr 1 — более быстрый вариант div 2 }
SwapItems(j, count + i := i - j);1
until Compare(sequence[i - 1], sequence[i]);
NextPermutation := j
{ Этап № 2 }
end;
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;
 
END.
</source>
 
Пример использования:
<source lang="pascal">
{ NarayanaTest.pas }
uses Narayana;
 
 
var sequence: array [0..3] of T; { Последовательность. Границы индексов могут быть и другими }
 
Write(sequence[0]);
for i := 1 to count - 1 do
Write(', ', sequence[i])
end;
WriteLn(']')
</source>
 
==[[w:Rust|Rust]]==
<source lang="rust">
// narayana.rs
// Поиск очередной перестановки
fn next_permutation <T: Copy + PartialOrd> (sequence: &mut[T], compare: fn (T, T) -> bool) -> usize {
let count = sequence.len();
let mut i = count;
// Этап № 1
loop {
if i < 2 {
return 0;
}
i -= 1;
if compare(sequence[i - 1], sequence[i]) {
break;
}
}
// Этап № 2
let mut j = count;
while j > i && !compare(sequence[i - 1], sequence[j - 1]) {
j -= 1;
}
i -= 1;
sequence.swap(i, j - 1);
// Этап № 3
j = i + 1;
while j <= (count + i) >> 1 { // >> 1 — более быстрый вариант / 2
sequence.swap(j, count + i - j);
j += 1;
}
j
}
</source>
Пример использования:
<source lang="rust">
// narayana_test.rs
// Возвращает true, если value_0 меньше value_1, иначе — false
fn less <T: PartialOrd> (value_0: T, value_1: T) -> bool {
value_0 < value_1
}
// Возвращает true, если value_0 больше value_1, иначе — false
fn greater <T: PartialOrd> (value_0: T, value_1: T) -> bool {
value_0 > value_1
}
// Инициализация последовательности
fn init_sequence (sequence: &mut [usize]) {
// Заполнение последовательности значениями 1, 2, 3…
let mut i = sequence.len();
while i > 0 {
sequence[i - 1] = i;
i -= 1;
}
}
// Основная программа
fn main () {
let mut sequence = [0usize; 4]; // Длина последовательности - 4. Может быть и любой другой
init_sequence(&mut sequence); // Формирование исходной последовательности
println!("Неубывающая последовательность и её перестановки:");
while {
println!("{:?}", sequence);
narayana::next_permutation(&mut sequence, less::<usize>) > 0 // x < y — критерий сравнения для неубывающей последовательности
} { }
println!("");
println!("Невозрастающая последовательность и её перестановки:");
while {
println!("{:?}", sequence);
narayana::next_permutation(&mut sequence, greater::<usize>) > 0 // x > y — критерий сравнения для невозрастающей последовательности
} { }
}
</source>
{{BookCat}}
74

правки