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

Добавлены реализации на VB.NET, Python и примеры их использования; скорректировано оформление программ на других языках
(Поправки к коду реализации на C)
(Добавлены реализации на VB.NET, Python и примеры их использования; скорректировано оформление программ на других языках)
 
=Реализации=
В нижеприведённых реализациях <code>sequence</code> — последовательность из <code>count</code> элементов, в которой производятся перестановки (как правило — массив из count элементов), <code>compare(x, y)</code> — функция, которая должна возвращать <code>true</code>значение «истина» если x < y и <code>false</code>«ложь» иначе (если исходный порядок элементов последовательности неубывающий; для невозрастающего исходного порядка условие меняется на x > y).
 
Если не оговорено другое, то функция поиска очередной перестановки возвращает значение «истина», если перестановка найдена, либо «ложь», если следующей перестановки не существует (перебор закончен).
 
==[[w:Бейсик|BASIC]]==
===[[w:Visual_Basic_.NET|VB.NET]]===
<source lang="vb">
' 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
</source>
Пример использования:
<source lang="vb">
' 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
</source>
 
==[[w:C (язык программирования)|C]]==
/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2);
 
/* Поиск очередной перестановки */
unsigned nextPermutation (T *sequence, unsigned const count, int (*compare)(T const, T const));
/* Обмен значениями двух элементов последовательности */
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)) {
}
 
/* Основная программа */
int main () {
unsigned count;
outputSequence(sequence, count);
} while (nextPermutation(sequence, count, &less)); /* x < y — критерий сравнения для неубывающей последовательности */
putchar('\n');
printf("Невозрастающая последовательность и её перестановки:\n");
do {
 
==[[w:C++|C++]]==
На основе итераторов. В качестве последовательности могут выступать не только массивы, но и другие контейнеры, поддерживающие последовательный доступ, например, списки.
На основе итераторов.
<source lang="cpp">
// narayana.hpp
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
return value_0 < value_1;
}
 
// Возвращает true, если value_0 больше value_1, иначе — false
template < typename T >
}
 
// Инициализация последовательности
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 << ']') << '\n';
}
 
template < typename Iterator >
void initSequence (Iterator const begin, Iterator const end) {
int i = 0;
for (Iterator current = begin; current != end; ++current)
*current = ++i;
}
 
// Narayana.java
abstract class Narayana {
// Функция, задающая отношение порядка для значений типа T: < либо >
@FunctionalInterface
interface Predicate2 <T extends Comparable> {
boolean compare (final T value_0, final T value_1);
}
// Обмен значениями двух элементов последовательности
static final private <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;
}
 
// Поиск очередной перестановки
static final public <T extends Comparable> boolean nextPermutation (T[] sequence, Predicate2 comparator) {
public static final <T extends Comparable> boolean nextPermutation (T[] sequence, Predicate2 comparator) {
// Этап № 1
int ji = sequence.length, i = j - 1;
do {
if (ji < 2)
return false; // Перебор закончен
} while (!comparator.compare(sequence[ --i], sequence[--j]));
} 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;
}
}
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) {
sequence[value - 1] = value;
}
 
// Основная программа
public static void main (String[] args) {
 
{ Поиск очередной перестановки }
function NextPermutation (var sequence: array of T; Compare: TPredicate2): WordBoolean;
 
IMPLEMENTATION
{ Обмен значениями двух элементов последовательности }
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
NextPermutation := false;
Exit
{ Перебор закончен }
end;
i := i - 1
while (j > i) and not Compare(sequence[i - 1], sequence[j - 1]) do
j := j - 1;
SwapItems(i :=- i1, j - 1);
SwapItems(i, j - 1);
{ Этап № 3 }
j := count;
for j := i + 1 to (count + i) shr 1 do { shr 1 — более быстрый вариант div 2 }
while (i < SwapItems(j,) count +and (i -< j - 1); do
begin
j := j - 1;
SwapItems(i, j);
i := i + 1
end;
NextPermutation := true
end;
 
 
var sequence: array of T;
var sequence: array [0..3] of T; { Последовательность. Границы индексов могут быть и другими }
count: Word;
 
{ Возвращает true, если value_0 меньше value_1, иначе — false }
{ Основная программа }
BEGIN
ReadLn(count);
SetLength(sequence, count);
InitSequence(sequence); { Формирование исходной последовательности }
WriteLn('Неубывающая последовательность и её перестановки:');
OutputSequence(sequence)
until not NextPermutation(sequence, @Less); { x < y — критерий сравнения для неубывающей последовательности }
WriteLn;
WriteLn('Невозрастающая последовательность и её перестановки:');
repeat
}
if (-1 == $k) {
return false; // Перебор закончен
}
// Этап № 2
print ‘<br/>’;
}
</source>
 
==[[w:Python|Python]]==
<source lang="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
</source>
Пример использования на Python 3.x (в Python 2.x надо убрать скобки в операторах <code>print</code>):
<source lang="python">
# 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
</source>
 
let mut i = count;
// Этап № 1
loopwhile {
if i < 2 {
return false; // Перебор закончен
}
i -= 1;
if !compare(sequence[i - 1], sequence[i]) {
} { } // Пустое тело цикла (имитация цикла с постусловием)
break;
}
}
// Этап № 2
let mut j = count;
j -= 1;
}
sequence.swap(i -= 1, j - 1);
sequence.swap(i, j - 1);
// Этап № 3
j = i + 1count;
while ji <= (countj +&& i) >>< 1j { // >>- 1 — более быстрый вариант / 2{
sequence.swap(j, count + i j -= j)1;
j += 1 sequence.swap(i, j);
i += 1;
}
true
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]) {
}
}
 
// Функция для ввода данных
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;
let mut sequence = [0usize; 4]; // Длина последовательности - 4. Может быть и любой другой
read_var(&mut count);
let mut sequence = vec![0usize; count];
init_sequence(&mut sequence); // Формирование исходной последовательности
println!("Неубывающая последовательность и её перестановки:");
narayana::next_permutation(&mut sequence, less::<usize>) // x < y — критерий сравнения для неубывающей последовательности
} { }
println!("");
println!("Невозрастающая последовательность и её перестановки:");
while {
74

правки