Реализации алгоритмов/Алгоритм Нарайаны: различия между версиями
Добавлена реализация и пример использования на Rust; мелкие правки для остальных языков |
Добавлена реализация и пример её использования на основе C++11 |
||
Строка 15: | Строка 15: | ||
Если не оговорено другое, то функция поиска очередной перестановки возвращает ненулевое значение, если перестановка найдена, либо 0, если следующей перестановки не существует (перебор закончен). |
Если не оговорено другое, то функция поиска очередной перестановки возвращает ненулевое значение, если перестановка найдена, либо 0, если следующей перестановки не существует (перебор закончен). |
||
==[[w:C (язык программирования)|C |
==[[w:C (язык программирования)|C]]== |
||
'''C:''' Тип <code>T</code> должен быть предварительно определён как: |
|||
<source lang="cpp"> |
<source lang="cpp"> |
||
⚫ | |||
typedef int T; /* Вместо int можно подставить любой тип */ |
typedef int T; /* Вместо int можно подставить любой тип */ |
||
⚫ | |||
'''C++:''' Все функции, кроме <code>main</code>, следует предварить строкой: |
|||
⚫ | |||
⚫ | |||
⚫ | |||
Собственно реализация: |
|||
⚫ | |||
⚫ | |||
/* Обмен значениями двух элементов последовательности */ |
/* Обмен значениями двух элементов последовательности */ |
||
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2); |
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2); |
||
Строка 35: | Строка 26: | ||
/* narayana.c |
/* narayana.c */ |
||
/* Обмен значениями двух элементов последовательности */ |
/* Обмен значениями двух элементов последовательности */ |
||
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2) { |
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2) { |
||
Строка 63: | Строка 54: | ||
Пример использования: |
Пример использования: |
||
<source lang="cpp"> |
<source lang="cpp"> |
||
/* narayana_test.c |
/* narayana_test.c */ |
||
#include <malloc.h> |
#include <malloc.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
Строка 103: | Строка 94: | ||
T *sequence = (T*)malloc(count * sizeof(T)); |
T *sequence = (T*)malloc(count * sizeof(T)); |
||
/* Для C++ заменить в предыдущей строке все T на int или любой другой тип, для которого определены операции < и > */ |
|||
initSequence(sequence, count); /* Формирование исходной последовательности */ |
initSequence(sequence, count); /* Формирование исходной последовательности */ |
||
printf("Неубывающая последовательность и её перестановки:\n"); |
printf("Неубывающая последовательность и её перестановки:\n"); |
||
Строка 115: | Строка 105: | ||
} while (nextPermutation(sequence, count, &greater)); /* x > y — критерий сравнения для невозрастающей последовательности */ |
} while (nextPermutation(sequence, count, &greater)); /* x > y — критерий сравнения для невозрастающей последовательности */ |
||
free(sequence); |
free(sequence); |
||
return 0; |
|||
} |
|||
⚫ | |||
==[[w:C++|C++]]== |
|||
Для C++11 или более позднего стандарта. На основе итераторов. |
|||
⚫ | |||
// 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; |
|||
} |
|||
} |
|||
⚫ | |||
Пример использования: |
|||
⚫ | |||
// narayana_test.cpp |
|||
#include <iostream> |
|||
#include "narayana.hpp" |
|||
⚫ | |||
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; |
return 0; |
||
} |
} |
Версия от 12:55, 21 мая 2017
Алгори́тм Нарайа́ны — нерекурсивный алгоритм, генерирующий по данной перестановке следующую за ней в лексикографическом порядке перестановку.
Алгоритм
Пусть — последовательность из элементов, для которых требуется найти очередную в лексикографическом порядке перестановку.
Алгоритм поиска очередной перестановки для последовательности с неубывающим (невозрастающим) изначальным порядком элементов:
- Найти наибольшее , для которого выполняется условие (). Если такого нет, значит все перестановки были сгенерированы.
- Найти наибольшее , для которого выполняется условие (). Затем поменять местами и .
- Элементы переставить в обратном порядке.
Реализации
В нижеприведённых реализациях sequence
— последовательность из count
элементов, в которой производятся перестановки (как правило — массив из count элементов), compare(x, y)
— функция, которая должна возвращать true
если x < y и false
иначе (если исходный порядок элементов последовательности неубывающий; для невозрастающего исходного порядка условие меняется на x > y).
Если не оговорено другое, то функция поиска очередной перестановки возвращает ненулевое значение, если перестановка найдена, либо 0, если следующей перестановки не существует (перебор закончен).
C
/* narayana.h */
typedef int T; /* Вместо int можно подставить любой тип */
/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2);
/* Поиск очередной перестановки */
unsigned nextPermutation (T *sequence, unsigned const count, int (*compare)(T const, T const));
/* narayana.c */
/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2) {
T _ = sequence[index_1]; /* _ — временная переменная */
sequence[index_1] = sequence[index_2];
sequence[index_2] = _;
}
/* Поиск очередной перестановки */
unsigned nextPermutation (T *sequence, unsigned count, int (*compare)(T const, T const)) {
unsigned i = count, j;
/* Этап № 1 */
do {
if (i < 2)
return 0;
--i;
} while (!(*compare)(sequence[i - 1], sequence[i]));
/* Этап № 2 */
for (j = count; j > i && !(*compare)(sequence[i - 1], sequence[j - 1]); --j);
--i;
_swapItems(sequence, i, j - 1);
/* Этап № 3 */
for (j = i + 1; j <= (count + i) >> 1; ++j) /* >> 1 — более быстрый вариант / 2 */
_swapItems(sequence, j, count + i - j);
return j;
}
Пример использования:
/* narayana_test.c */
#include <malloc.h>
#include <stdio.h>
#include "narayana.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));
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;
}
C++
Для C++11 или более позднего стандарта. На основе итераторов.
// 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;
}
}
Пример использования:
// 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;
}
Pascal
{ Narayana.pas }
UNIT Narayana;
INTERFACE
type T = Integer; { Вместо Integer можно использовать любой тип }
{ Функция, задающая отношение порядка для значений типа T: < либо > }
TPredicate2 = function (const value_0, value_1: T): Boolean;
{ Поиск очередной перестановки }
function NextPermutation (var sequence: array of T; Compare: TPredicate2): Word;
IMPLEMENTATION
{ Поиск очередной перестановки }
function NextPermutation (var sequence: array of T; Compare: TPredicate2): Word;
var count, i, j: Word;
{ Обмен значениями двух элементов последовательности }
procedure SwapItems (index_1, index_2: Word);
var _: T; { _ — временная переменная }
begin
_ := sequence[index_1];
sequence[index_1] := sequence[index_2];
sequence[index_2] := _
end;
begin
count := Length(sequence);
{ Этап № 1 }
i := count;
repeat
if i < 2 then
begin
NextPermutation := 0;
Exit
end;
i := i - 1
until Compare(sequence[i - 1], sequence[i]);
{ Этап № 2 }
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.
Пример использования:
{ NarayanaTest.pas }
uses Narayana;
var sequence: array [0..3] of T; { Последовательность. Границы индексов могут быть и другими }
{ Возвращает true, если value_0 меньше value_1, иначе — false }
function Less (const value_0, value_1: T): Boolean;
begin
Less := value_0 < value_1
end;
{ Возвращает true, если value_0 больше value_1, иначе — false }
function Greater (const value_0, value_1: T): Boolean;
begin
Greater := value_0 > value_1
end;
{ Инициализация последовательности }
procedure InitSequence (var sequence: array of T);
var i: Word;
begin
{ Заполнение последовательности значениями 1, 2, 3… }
for i := Length(sequence) downTo 1 do
sequence[i - 1] := i;
end;
{ Вывод содержимого последовательности }
procedure OutputSequence (const sequence: array of T);
var i, count: Word;
begin
Write('[');
count := Length(sequence);
if count > 0 then { Если последовательность не пуста }
begin
Write(sequence[0]);
for i := 1 to count - 1 do
Write(', ', sequence[i])
end;
WriteLn(']')
end;
{ Основная программа }
BEGIN
InitSequence(sequence); { Формирование исходной последовательности }
WriteLn('Неубывающая последовательность и её перестановки:');
repeat
OutputSequence(sequence)
until NextPermutation(sequence, @Less) = 0; { x < y — критерий сравнения для неубывающей последовательности }
WriteLn;
WriteLn('Невозрастающая последовательность и её перестановки:');
repeat
OutputSequence(sequence)
until NextPermutation(sequence, @Greater) = 0 { x > y — критерий сравнения для невозрастающей последовательности }
END.
PHP
Вариант № 1
function nextPermutation ($sequence, $count) {
$out = $sequence;
// Этап № 1
$k = $count - 2;
while ($k >= 0 && $out[$k] >= $out[$k + 1]) {
--$k;
}
if (-1 == $k) {
return false;
}
// Этап № 2
$t = $count - 1;
while ($t >= 0 && $t >= $k + 1 && $out[$k] >= $out[$t]) {
--$t;
}
$tmp = $out[$k];
$out[$k] = $out[$t];
$out[$t] = $tmp;
// Этап № 3
for ($i = $k + 1; $i < ceil(($count + $k) / 2); ++$i) {
$t = $count + $k - $i;
$tmp = $out[$i];
$out[$i] = $out[$t];
$out[$t] = $tmp;
}
return $out;
}
Вариант № 2
Вариант с выводом справа налево:
$b = "123456789";
$a = strrev($b);
while ($a !=$b) {
$i = 0;
while($a[$i] > $a[$i - 1]) {
$i++;
}
$j = 0;
while($a[$j] < $a[$i]) {
++$j;
}
$c = $a[$j];
$a[$j] = $a[$i];
$a[$i] = $c;
$x = strrev(substr($a, 0, $i));
$y = substr($a, $i);
print $a = $x . $y;
print ‘<br/>’;
}
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
}
Пример использования:
// 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 — критерий сравнения для невозрастающей последовательности
} { }
}