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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Добавлена реализация и пример использования на Rust; мелкие правки для остальных языков
Добавлена реализация и пример её использования на основе C++11
Строка 15: Строка 15:
Если не оговорено другое, то функция поиска очередной перестановки возвращает ненулевое значение, если перестановка найдена, либо 0, если следующей перестановки не существует (перебор закончен).
Если не оговорено другое, то функция поиска очередной перестановки возвращает ненулевое значение, если перестановка найдена, либо 0, если следующей перестановки не существует (перебор закончен).


==[[w:C (язык программирования)|C]]/[[w:C++|C++]]==
==[[w:C (язык программирования)|C]]==
'''C:''' Тип <code>T</code> должен быть предварительно определён как:
<source lang="cpp">
<source lang="cpp">
/* narayana.h */
typedef int T; /* Вместо int можно подставить любой тип */
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);
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2);
Строка 35: Строка 26:




/* narayana.c или narayana.cpp */
/* 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.cpp */
/* 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;
}
</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;
return 0;
}
}

Версия от 12:55, 21 мая 2017

Алгори́тм Нарайа́ны — нерекурсивный алгоритм, генерирующий по данной перестановке следующую за ней в лексикографическом порядке перестановку.

Алгоритм

Пусть  — последовательность из элементов, для которых требуется найти очередную в лексикографическом порядке перестановку.

Алгоритм поиска очередной перестановки для последовательности с неубывающим (невозрастающим) изначальным порядком элементов:

  1. Найти наибольшее , для которого выполняется условие (). Если такого нет, значит все перестановки были сгенерированы.
  2. Найти наибольшее , для которого выполняется условие (). Затем поменять местами и .
  3. Элементы переставить в обратном порядке.

Реализации

В нижеприведённых реализациях 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 — критерий сравнения для невозрастающей последовательности
    } { }
}