Реализации алгоритмов/Алгоритм Нарайаны

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

Алгоритм

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

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

1. Найти наибольшее $i$, для которого выполняется условие $sequence_{i}<sequence_{i+1}$ ($sequence_{i}>sequence_{i+1}$). Если такого нет, значит все перестановки были сгенерированы.
2. Найти наибольшее $j>i$, для которого выполняется условие $sequence_{i}<sequence_{j}$ ($sequence_{i}>sequence_{j}$). Затем поменять местами $sequence_{i}$ и $sequence_{j}$.
3. Элементы $sequence_{i+1},...,sequence_{count}$ переставить в обратном порядке.

Реализации

В нижеприведённых реализациях sequence — последовательность из count элементов, в которой производятся перестановки (как правило — массив из count элементов), compare(x, y) — функция, которая должна возвращать значение «истина» если x < y и «ложь» иначе (если исходный порядок элементов последовательности неубывающий; для невозрастающего исходного порядка условие меняется на x > y).

Если не оговорено другое, то функция поиска очередной перестановки возвращает значение «истина», если перестановка найдена, либо «ложь», если следующей перестановки не существует (перебор закончен).

BASIC

VB.NET

' Narayana.vb
Module Narayana
        ''' <summary>
    ''' Функция, задающая отношение порядка для значений типа T: < либо >
    ''' </summary>
    Public Delegate Function Predicate2 (Of T)(ByVal value_0 As T, ByVal value_1 As T) As Boolean
 
    ''' <summary>
    ''' Поиск очередной перестановки
    ''' </summary>
    Public Function NextPermutation (Of T)(ByRef sequence As T(), compare As Predicate2(Of T)) As Boolean
        ' Этап № 1
        Dim i As Integer = sequence.Length
        Do
            If i < 2 Then Return False ' Перебор закончен
            i -= 1
        Loop Until compare(sequence(i - 1), sequence(i))
        ' Этап № 2
        Dim j As Integer = sequence.Length
        Do While i < j And Not compare(sequence(i - 1), sequence(j - 1))
            j -= 1
        Loop
        _SwapItems(Of T)(sequence, i - 1, j - 1)
        ' Этап № 3
        j = sequence.Length
        Do While i < j And i < j - 1
            j -= 1
            _SwapItems(Of T)(sequence, i, j)
            i += 1
        Loop
        Return True
    End Function

    ''' <summary>
    ''' Обмен значениями двух элементов последовательности
    ''' </summary>
    Private Sub _SwapItems (Of T)(ByRef sequence As T(), ByVal index_0 As Integer, ByVal index_1 As Integer)
        Dim item As T = sequence(index_0)
        sequence(index_0) = sequence(index_1)
        sequence(index_1) = item
    End Sub
End Module

Пример использования:

' NarayanaTest.vb
Module NarayanaTest
    ''' <summary>
    ''' Возвращает True, если value_0 меньше value_1, иначе — False
    ''' </summary>
    Function Less (Of T As IComparable)(ByVal value_0 As Integer, ByVal value_1 As Integer) As Boolean
        Return value_0.CompareTo(value_1) < 0
    End Function

    ''' <summary>
    ''' Возвращает True, если value_0 больше value_1, иначе — False
    ''' </summary>
    Function Greater (Of T As IComparable)(ByVal value_0 As Integer, ByVal value_1 As Integer) As Boolean
        Return value_0.CompareTo(value_1) > 0
    End Function

    ''' <summary>
    ''' Инициализация последовательности
    ''' </summary>
    Sub InitSequence (ByRef sequence As Integer())
        For i As Integer = sequence.Length To 1 Step -1
            sequence(i - 1) = i
        Next
    End Sub

    ''' <summary>
    ''' Вывод содержимого последовательности
    ''' </summary>
    Sub OutputSequence (Of T)(ByVal sequence As T())
        Console.Write("["C)
        If sequence IsNot Nothing And sequence.Length > 0 Then
            Console.Write(sequence(0))
            For i As Integer = 1 To sequence.GetUpperBound(0)
                Console.Write(", ")
                Console.Write(sequence(i))
            Next
        End If
        Console.WriteLine("]"C)
    End Sub

    ''' <summary>
    ''' Основная программа
    ''' </summary>
    Public Sub Main ()
        Dim count As Integer = Integer.Parse(Console.ReadLine())
        Dim sequence(count - 1) As Integer
        InitSequence(Of Integer)(sequence)
        Console.WriteLine("Неубывающая последовательность и её перестановки:")
        Do
            OutputSequence(Of Integer)(sequence)
        Loop While Narayana.NextPermutation(Of Integer)(sequence, AddressOf Less(Of Integer))
        Console.WriteLine("Невозрастающая последовательность и её перестановки:")
        Do
            OutputSequence(Of Integer)(sequence)
        Loop While Narayana.NextPermutation(sequence, AddressOf Greater(Of Integer))
    End Sub
End Module

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 */
#include "narayana.h"


/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2) {
    T item = sequence[index_1];
    sequence[index_1] = sequence[index_2];
    sequence[index_2] = item;
}

/* Поиск очередной перестановки */
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);
    _swapItems(sequence, i - 1, j - 1);
    /* Этап № 3 */
    for (j = count; i < j && i < --j; )
		_swapItems(sequence, i++, j);
    return 1;
}

Пример использования:

/* 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… */
    unsigned i;
    for (i = count; i; --i)
        sequence[i - 1] = i;
}

/* Вывод содержимого последовательности */
void outputSequence (T const *sequence, unsigned count) {
    putchar('[');
    if (count) { /* Если последовательность не пуста */
        unsigned i;
        printf("%d", sequence[0]);
        for (i = 1; i < count; ++i)
            printf(", %d", sequence[i]);
    }
    putchar(']');
    putchar('\n');
}

/* Основная программа */
int main () {
    unsigned count;
    scanf("%d", &count);
    T *sequence = (T*)malloc(count * sizeof(T));
    initSequence(sequence, count); /* Формирование исходной последовательности */
    printf("Неубывающая последовательность и её перестановки:\n");
    do {
        outputSequence(sequence, count);
    } while (nextPermutation(sequence, count, &less)); /* x < y — критерий сравнения для неубывающей последовательности */
    printf("Невозрастающая последовательность и её перестановки:\n");
    do {
        outputSequence(sequence, count);
    } while (nextPermutation(sequence, count, &greater)); /* x > y — критерий сравнения для невозрастающей последовательности */
    free(sequence);
    return 0;
}

C++

На основе итераторов. В качестве последовательности могут выступать не только массивы, но и другие контейнеры, поддерживающие последовательный доступ, например, списки.

// narayana.hpp
namespace Narayana {
    // Обмен значениями двух элементов последовательности
    template < typename T >
    static void _swap (T &variable_0, T &variable_1) {
        T variable = variable_0;
        variable_0 = variable_1;
        variable_1 = variable;
    }

    // Поиск очередной перестановки
    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));
        _swap(*i, *j);
        // Этап № 3
        ++i;
        j = end;
        for ( ; (i != j) && (i != --j); ++i)
            _swap(*i, *j);
        return true;
    }
}

Пример использования:

// narayana_test.cpp
#include <iostream>

#include "narayana.hpp"


// Возвращает true, если value_0 меньше value_1, иначе — false
template < typename T >
bool less (T value_0, T value_1) {
    return value_0 < value_1;
}

// Возвращает true, если value_0 больше value_1, иначе — false
template < typename T >
bool greater (T value_0, T value_1) {
    return value_0 > value_1;
}

// Инициализация последовательности
template < typename Iterator >
void initSequence (Iterator const begin, Iterator const end) {
    int i = 0;
    for (Iterator current = begin; current != end; ++current)
        *current = ++i;
}

// Вывод содержимого последовательности
template < typename Iterator >
void outputSequence (Iterator const begin, Iterator const end) {
    std::cout << '[';
    if (begin != end) {
        std::cout << *begin;
        for (Iterator current = begin; ++current != end; )
            ((std::cout << ',') << ' ') << *current;
    }
    (std::cout << ']') << '\n';
}

int main () {
    unsigned count;
    std::cin >> count;
    int *sequence = new int[count], *sequence_end = sequence + count;
    initSequence(sequence, sequence_end); // Формирование исходной последовательности
    std::cout << "Неубывающая последовательность и её перестановки:\n";
    do {
        outputSequence(sequence, sequence_end);
    } while (Narayana::nextPermutation(sequence, sequence_end, &less<int>)); // x < y — критерий сравнения для неубывающей последовательности
    std::cout << "Невозрастающая последовательность и её перестановки:\n";
    do {
        outputSequence(sequence, sequence_end);
    } while (Narayana::nextPermutation(sequence, sequence_end, &greater<int>)); // x > y — критерий сравнения для невозрастающей последовательности
    delete [] sequence;
    return 0;
}

Java

// Narayana.java
abstract class Narayana {
    // Функция, задающая отношение порядка для значений типа T: < либо >
    @FunctionalInterface
    interface Predicate2 <T extends Comparable> {
        boolean compare (final T value_0, final T value_1);
    }

    // Поиск очередной перестановки
    public static final <T extends Comparable> boolean nextPermutation (T[] sequence, Predicate2 comparator) {
        // Этап № 1
        int i = sequence.length;
        do {
            if (i < 2)
                return false; // Перебор закончен
            --i;
        } while (!comparator.compare(sequence[i - 1], sequence[i]));
        // Этап № 2
        int j = sequence.length;
        while (i < j && !comparator.compare(sequence[i - 1], sequence[--j]));
        _swapItems(sequence, i - 1, j);
        // Этап № 3
        j = sequence.length;
        while (i < j && i < --j)
            _swapItems(sequence, i++, j);
        return true;
    }

    // Обмен значениями двух элементов последовательности
    private static final <T> void _swapItems (T[] sequence, int index_0, int index_1) {
        T temp = sequence[index_0];
        sequence[index_0] = sequence[index_1];
        sequence[index_1] = temp;
    }
}

Пример использования:

// NarayanaTest.java
import java.util.Arrays;
import java.util.Scanner;


public class NarayanaTest {
    // Возвращает true, если value_0 меньше value_1, иначе — false
    static final <T extends Comparable> boolean less (final T value_0, final T value_1) {
        return value_0.compareTo(value_1) < 0;
    }

    // Возвращает true, если value_0 больше value_1, иначе — false
    static final <T extends Comparable> boolean greater (final T value_0, final T value_1) {
        return value_0.compareTo(value_1) > 0;
    }

    // Инициализация последовательности
    static final void initSequence (Integer[] sequence) {
        for (int value = sequence.length; value > 0; --value)
            sequence[value - 1] = value;
    }

    // Основная программа
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        Integer[] sequence = new Integer[count];
        initSequence(sequence); // Формирование исходной последовательности
        System.out.println("Неубывающая последовательность и её перестановки:");
        do {
            System.out.println(Arrays.deepToString(sequence));
        } while (Narayana.nextPermutation(sequence, NarayanaTest::less)); // x < y — критерий сравнения для неубывающей последовательности
        System.out.println("Невозрастающая последовательность и её перестановки:");
        do {
            System.out.println(Arrays.deepToString(sequence));
        } while (Narayana.nextPermutation(sequence, NarayanaTest::greater)); // x > y — критерий сравнения для невозрастающей последовательности
     }
}

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): Boolean;

IMPLEMENTATION

    { Поиск очередной перестановки }
    function NextPermutation (var sequence: array of T; Compare: TPredicate2): Boolean;
    var count, i, j: Word;
        { Обмен значениями двух элементов последовательности }
        procedure SwapItems (index_1, index_2: Word);
        var item: T;
        begin
            item := sequence[index_1];
            sequence[index_1] := sequence[index_2];
            sequence[index_2] := item
        end;
    begin
        count := Length(sequence);
        { Этап № 1 }
        i := count;
        repeat
            if i < 2 then
            begin
                NextPermutation := false;
                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;
        SwapItems(i - 1, j - 1);
        { Этап № 3 }
        j := count;
        while (i < j) and (i < j - 1) do
        begin
            j := j - 1;
            SwapItems(i, j);
            i := i + 1
        end;
        NextPermutation := true
    end;

END.

Пример использования:

{ NarayanaTest.pas }
uses Narayana;


var sequence: array of T;
    count: Word;

{ Возвращает 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
    ReadLn(count);
    SetLength(sequence, count);
    InitSequence(sequence); { Формирование исходной последовательности }
    WriteLn('Неубывающая последовательность и её перестановки:');
    repeat
        OutputSequence(sequence)
    until not NextPermutation(sequence, @Less); { x < y — критерий сравнения для неубывающей последовательности }
    WriteLn('Невозрастающая последовательность и её перестановки:');
    repeat
        OutputSequence(sequence)
    until not NextPermutation(sequence, @Greater) { 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/>’;
}

Python

# narayana.py
"""Поиск очередной перестановки"""
def next_permutation (sequence, compare):
    count = len(sequence)
    i = count
    # Этап № 1
    while True:
        if i < 2:
            return False # Перебор закончен
        i -= 1;
        if compare(sequence[i - 1], sequence[i]):
            break
    # Этап № 2
    j = count
    while j > i and not compare(sequence[i - 1], sequence[j - 1]):
        j -= 1
    sequence[i - 1], sequence[j - 1] = sequence[j - 1], sequence[i - 1]
    # Этап № 3
    j = count
    while i < j and i < j - 1:
        j -= 1
        sequence[i], sequence[j] = sequence[j], sequence[i]
        i += 1
    return True

Пример использования на Python 3.x (в Python 2.x надо убрать скобки в операторах print):

# narayana_test.py
import narayana


"""Возвращает True, если value_0 меньше value_1, иначе — False"""
def less (value_0, value_1):
    return value_0 < value_1

"""Возвращает True, если value_0 больше value_1, иначе — False"""
def greater (value_0, value_1):
    return value_0 > value_1

# Основная программа
count = int(input());
sequence = list(range(1, count + 1)) # Формирование исходной последовательности
print("Неубывающая последовательность и её перестановки:")
while True:
    print(sequence)
    if not narayana.next_permutation(sequence, less): # x < y — критерий сравнения для неубывающей последовательности
        break
print("Невозрастающая последовательность и её перестановки:")
while True:
    print(sequence)
    if not narayana.next_permutation(sequence, greater): # x > y — критерий сравнения для невозрастающей последовательности
        break

Rust

// narayana.rs
// Поиск очередной перестановки
fn next_permutation <T: Copy + PartialOrd> (sequence: &mut[T], compare: fn (T, T) -> bool) -> bool {
    let count = sequence.len();
    let mut i = count;
    // Этап № 1
    while {
        if i < 2 {
            return false; // Перебор закончен
        }
        i -= 1;
        !compare(sequence[i - 1], sequence[i])
    } { } // Пустое тело цикла (имитация цикла с постусловием)
    // Этап № 2
    let mut j = count;
    while j > i && !compare(sequence[i - 1], sequence[j - 1]) {
        j -= 1;
    }
    sequence.swap(i - 1, j - 1);
    // Этап № 3
    j = count;
    while i < j && i < j - 1 {
        j -= 1;
        sequence.swap(i, j);
        i += 1;
    }
    true
}

Пример использования:

// 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 read_var <Type: std::str::FromStr> (var: &mut Type) -> bool {
    let mut input_text = String::new();
    std::io::stdin()
        .read_line(&mut input_text)
        .expect("failed to read from stdin");
    match input_text.trim().parse::<Type>() {
        Ok(value) => { *var = value; true },
        Err(..) => { false }
    }
}

// Основная программа
fn main () {
    let mut count = 0usize;
    read_var(&mut count);
    let mut sequence = vec![0usize; count];
    init_sequence(&mut sequence); // Формирование исходной последовательности
    println!("Неубывающая последовательность и её перестановки:");
    while {
        println!("{:?}", sequence);
        narayana::next_permutation(&mut sequence, less::<usize>) // x < y — критерий сравнения для неубывающей последовательности
    } { }
    println!("Невозрастающая последовательность и её перестановки:");
    while {
        println!("{:?}", sequence);
        narayana::next_permutation(&mut sequence, greater::<usize>) // x > y — критерий сравнения для невозрастающей последовательности
    } { }
}