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

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

Алгоритм

Пусть $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

Visual Basic .NET

' Narayana.vb

Public 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)(ByVal sequence As T(), ByVal 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(sequence, i - 1, j - 1)
		' Этап № 3
		j = sequence.Length
		Do While i < j - 1
			j -= 1
			_SwapItems(sequence, i, j)
			i += 1
		Loop
		Return True
	End Function

	''' <summary>
	''' Обмен значениями двух элементов последовательности
	''' </summary>
	Private Sub _SwapItems(Of T)(ByVal 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>
	Private Function Less(Of T As IComparable)(ByVal value_0 As T, ByVal value_1 As T) As Boolean
		Return value_0.CompareTo(value_1) < 0
	End Function

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

	''' <summary>
	''' Инициализация последовательности
	''' </summary>
	Private Sub InitSequence(ByVal sequence As Integer())
		' Заполнение последовательности значениями 1, 2, 3…
		For i As Integer = sequence.Length To 1 Step -1
			sequence(i - 1) = i
		Next
	End Sub

	''' <summary>
	''' Вывод содержимого последовательности
	''' </summary>
	Private 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(ByVal args As String())
		Dim count As Integer = Integer.Parse(Console.ReadLine())
		Dim sequence(count - 1) As Integer
		InitSequence(sequence) ' Формирование исходной последовательности
		Console.WriteLine("Неубывающая последовательность и её перестановки:")
		Do
			OutputSequence(sequence)
		Loop While Narayana.NextPermutation(sequence, AddressOf Less)
		' x < y — критерий сравнения для неубывающей последовательности
		Console.WriteLine("Невозрастающая последовательность и её перестановки:")
		Do
			OutputSequence(sequence)
		Loop While Narayana.NextPermutation(sequence, AddressOf Greater)
		' x > y — критерий сравнения для невозрастающей последовательности
	End Sub
End Module

C

/* narayana.h */

#ifndef _NARAYANA_H_
#define _NARAYANA_H_

typedef int T; /* Вместо int можно подставить любой тип */

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

/* Поиск очередной перестановки */
unsigned nextPermutation(T *sequence, unsigned const count, int (*compare)(T const, T const));

#endif


/* narayana.c */

#include "narayana.h"

/* Обмен значениями двух элементов последовательности */
static void _swapItems(T *sequence, unsigned index_0, unsigned index_1) {
	T item = sequence[index_0];
	sequence[index_0] = sequence[index_1];
	sequence[index_1] = 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]); );
	_swapItems(sequence, i - 1, j);
	/* Этап № 3 */
	for (j = count; 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

#ifndef _NARAYANA_HPP_
#define _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;
	}
}

#endif

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

// 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) {
	// Заполнение последовательности значениями 1, 2, 3…
	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;
}

C#

// Narayana.cs

public static class Narayana {
	/// <summary>
	/// Функция, задающая отношение порядка для значений типа T: < либо >
	/// </summary>
	public delegate bool Predicate2<T>(T value_0, T value_1);
 
	/// <summary>
	/// Поиск очередной перестановки
	/// </summary>
	public static bool NextPermutation<T>(T[] sequence, Predicate2<T> compare)
	{
		// Этап № 1
		var i = sequence.Length;
		do
		{
			if (i < 2)
			return false; // Перебор закончен
			--i;
		} while (!compare(sequence[i - 1], sequence[i]));
		// Этап № 2
		var j = sequence.Length;
		while (i < j && !compare(sequence[i - 1], sequence[--j]));
		_SwapItems(sequence, i - 1, j);
		// Этап № 3
		j = sequence.Length;
		while (i < --j)
			_SwapItems(sequence, i++, j);
		return true;
	}

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

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

// NarayanaTest.cs

public static class NarayanaTest
{
	/// <summary>
	/// Возвращает true, если value_0 меньше value_1, иначе — false
	/// </summary>
	private static bool Less<T>(T value_0, T value_1) where T: System.IComparable
	{
		return value_0.CompareTo(value_1) < 0;
	}

	/// <summary>
	/// Возвращает true, если value_0 больше value_1, иначе — false
	/// </summary>
	private static bool Greater<T>(T value_0, T value_1) where T: System.IComparable
	{
		return value_0.CompareTo(value_1) > 0;
	}

	/// <summary>
	/// Инициализация последовательности
	/// </summary>
	private static void InitSequence(int[] sequence)
	{
		// Заполнение последовательности значениями 1, 2, 3…
		for (var i = sequence.Length; i > 0; --i)
			sequence[i - 1] = i;
	}

	/// <summary>
	/// Вывод содержимого последовательности
	/// </summary>
	private static void OutputSequence<T>(T[] sequence)
	{
		System.Console.Write('[');
		if (!(sequence == null) && (sequence.Length > 0))
		{
			System.Console.Write(sequence[0]);
			for (var i = 1; i < sequence.Length; ++i)
			{
				System.Console.Write(", ");
				System.Console.Write(sequence[i]);
			}
		}
		System.Console.WriteLine(']');
	}

	/// <summary>
	/// Основная программа
	/// </summary>
	public static void Main()
	{
		var count = int.Parse(System.Console.ReadLine());
		var sequence = new int[count];
		InitSequence(sequence); // Формирование исходной последовательности
		System.Console.WriteLine("Неубывающая последовательность и её перестановки:");
		do
		{
			OutputSequence(sequence);
		} while (Narayana.NextPermutation(sequence, Less));
		// x < y — критерий сравнения для неубывающей последовательности
		System.Console.WriteLine("Невозрастающая последовательность и её перестановки:");
		do
		{
			OutputSequence(sequence);
		} while (Narayana.NextPermutation(sequence, Greater));
		// x > y — критерий сравнения для невозрастающей последовательности
	}
}

Go

// narayana/narayana.go

package narayana

type T = int // Вместо int можно подставить любой тип

// Поиск очередной перестановки
func NextPermutation(sequence []T, compare func (T, T) bool) bool {
	count := len(sequence)
	i := count
	// Этап № 1
	for {
		if i < 2 {
			return false // Перебор закончен
		}
		i--
		if compare(sequence[i - 1], sequence[i]) {
			break
		}
	}
	// Этап № 2
	j := count
	for j > i && !compare(sequence[i - 1], sequence[j - 1]) {
		j--
	}
	sequence[i - 1], sequence[j - 1] = sequence[j - 1], sequence[i - 1]
	// Этап № 3
	j = count
	for i < j - 1 {
		j--
		sequence[i], sequence[j] = sequence[j], sequence[i]
		i++
	}
	return true
}

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

// narayana_test.go

package main

import (
	"fmt",
	"narayana"
)

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

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

// Инициализация последовательности
func initSequence(sequence []narayana.T) {
	// Заполнение последовательности значениями 1, 2, 3…
	value := narayana.T(len(sequence))
	for i := len(sequence); i > 0; {
		i--
		sequence[i] = value
		value--
	}
}

func main() {
	var count uint
	fmt.Scan(&count)
	var sequence := make([]narayana.T, count)
	initSequence(sequence) // Формирование исходной последовательности
	fmt.Println("Неубывающая последовательность и её перестановки:")
	for {
		fmt.Println(sequence)
		if !narayana.NextPermutation(sequence, less) {
			break
		}
		// x < y — критерий сравнения для неубывающей последовательности
	}
	fmt.Println("Невозрастающая последовательность и её перестановки:")
	for {
		fmt.Println(sequence)
		if !narayana.NextPermutation(sequence, greater) {
			break
		}
		// x > y — критерий сравнения для невозрастающей последовательности
	}
	sequence = nil
}

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)
			_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) {
		// Заполнение последовательности значениями 1, 2, 3…
		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 - 1 do
		begin
			j := j - 1;
			SwapItems(i, j);
			i := i + 1
		end;
		NextPermutation := true
	end;

END.

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

{ NarayanaTest.pas }

PROGRAM NarayanaTest;

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

// narayana.php

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

Вариант с выводом справа налево:

// narayana.php

$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) -> bool:
	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 - 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)) # Заполнение последовательности значениями 1, 2, 3…
print("Неубывающая последовательность и её перестановки:")
permutation_found = True
while permutation_found:
	print(sequence)
	permutation_found = narayana.next_permutation(sequence, less)
	# x < y — критерий сравнения для неубывающей последовательности
print("Невозрастающая последовательность и её перестановки:")
permutation_found = True
while permutation_found:
	print(sequence)
	permutation_found = narayana.next_permutation(sequence, greater)
	# x > y — критерий сравнения для невозрастающей последовательности

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 - 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 [i32]) {
	// Заполнение последовательности значениями 1, 2, 3…
	let mut i = sequence.len();
	let mut value = i as i32;
	while i > 0 {
		i -= 1;
		sequence[i] = value;
		value -= 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("Не удалось прочитать из стандартного ввода.");
	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![0i32; count];
	init_sequence(&mut sequence); // Формирование исходной последовательности
	println!("Неубывающая последовательность и её перестановки:");
	while {
		println!("{:?}", sequence);
		narayana::next_permutation(&mut sequence, less::<i32>)
		// x < y — критерий сравнения для неубывающей последовательности
	} { }
	println!("Невозрастающая последовательность и её перестановки:");
	while {
		println!("{:?}", sequence);
		narayana::next_permutation(&mut sequence, greater::<i32>)
		// x > y — критерий сравнения для невозрастающей последовательности
	} { }
}