Реализации алгоритмов/Алгоритм Нарайаны: различия между версиями
Содержимое удалено Содержимое добавлено
Поправки к коду реализации на C |
Добавлены реализации на VB.NET, Python и примеры их использования; скорректировано оформление программ на других языках |
||
Строка 11:
=Реализации=
В нижеприведённых реализациях <code>sequence</code> — последовательность из <code>count</code> элементов, в которой производятся перестановки (как правило — массив из count элементов), <code>compare(x, y)</code> — функция, которая должна возвращать
Если не оговорено другое, то функция поиска очередной перестановки возвращает значение «истина», если перестановка найдена, либо «ложь», если следующей перестановки не существует (перебор закончен).
==[[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]]==
Строка 22 ⟶ 129 :
/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2);
/* Поиск очередной перестановки */
unsigned nextPermutation (T *sequence, unsigned const count, int (*compare)(T const, T const));
Строка 32 ⟶ 140 :
/* Обмен значениями двух элементов последовательности */
static void _swapItems (T *sequence, unsigned index_1, unsigned index_2) {
T
sequence[index_1] = sequence[index_2];
sequence[index_2] =
}
/* Поиск очередной перестановки */
unsigned nextPermutation (T *sequence, unsigned count, int (*compare)(T const, T const)) {
Строка 94 ⟶ 203 :
}
/* Основная программа */
int main () {
unsigned count;
Строка 103 ⟶ 213 :
outputSequence(sequence, count);
} while (nextPermutation(sequence, count, &less)); /* x < y — критерий сравнения для неубывающей последовательности */
printf("Невозрастающая последовательность и её перестановки:\n");
do {
Строка 114 ⟶ 223 :
==[[w:C++|C++]]==
На основе итераторов. В качестве последовательности могут выступать не только массивы, но и другие контейнеры, поддерживающие последовательный доступ, например, списки.
<source lang="cpp">
// narayana.hpp
Строка 125 ⟶ 234 :
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
Строка 163 ⟶ 273 :
return value_0 < value_1;
}
// Возвращает true, если value_0 больше value_1, иначе — false
template < typename T >
Строка 169 ⟶ 280 :
}
// Инициализация последовательности
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) {
Строка 178 ⟶ 298 :
}
(std::cout << ']') << '\n';
}
Строка 209 ⟶ 322 :
// 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
do {
if (
return false; // Перебор закончен
--i;
} while (!comparator.compare(sequence[ // Этап № 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 (
_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;
}
}
Строка 252 ⟶ 368 :
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) {
Строка 261 ⟶ 379 :
sequence[value - 1] = value;
}
// Основная программа
public static void main (String[] args) {
Строка 291 ⟶ 410 :
{ Поиск очередной перестановки }
function NextPermutation (var sequence: array of T; Compare: TPredicate2):
IMPLEMENTATION
Строка 300 ⟶ 419 :
{ Обмен значениями двух элементов последовательности }
procedure SwapItems (index_1, index_2: Word);
var
begin
sequence[index_1] := sequence[index_2];
sequence[index_2] :=
end;
begin
Строка 315 ⟶ 434 :
NextPermutation := false;
Exit
{ Перебор закончен }
end;
i := i - 1
Строка 322 ⟶ 442 :
while (j > i) and not Compare(sequence[i - 1], sequence[j - 1]) do
j := j - 1;
SwapItems(i
{ Этап № 3 }
j := count;
while (i <
begin
j := j - 1;
SwapItems(i, j);
i := i + 1
end;
NextPermutation := true
end;
Строка 339 ⟶ 463 :
var sequence: array of T;
count: Word;
{ Возвращает true, если value_0 меньше value_1, иначе — false }
Строка 379 ⟶ 504 :
{ Основная программа }
BEGIN
ReadLn(count);
SetLength(sequence, count);
InitSequence(sequence); { Формирование исходной последовательности }
WriteLn('Неубывающая последовательность и её перестановки:');
Строка 384 ⟶ 511 :
OutputSequence(sequence)
until not NextPermutation(sequence, @Less); { x < y — критерий сравнения для неубывающей последовательности }
WriteLn('Невозрастающая последовательность и её перестановки:');
repeat
Строка 403 ⟶ 529 :
}
if (-1 == $k) {
return false; // Перебор закончен
}
// Этап № 2
Строка 451 ⟶ 577 :
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>
Строка 461 ⟶ 643 :
let mut i = count;
// Этап № 1
if i < 2 {
return false; // Перебор закончен
}
i -= 1;
} { } // Пустое тело цикла (имитация цикла с постусловием)
// Этап № 2
let mut j = count;
Строка 475 ⟶ 655 :
j -= 1;
}
sequence.swap(i -
// Этап № 3
j =
while
i += 1;
}
true
Строка 493 ⟶ 673 :
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]) {
Строка 506 ⟶ 688 :
}
}
// Функция для ввода данных
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!("Неубывающая последовательность и её перестановки:");
Строка 515 ⟶ 712 :
narayana::next_permutation(&mut sequence, less::<usize>) // x < y — критерий сравнения для неубывающей последовательности
} { }
println!("Невозрастающая последовательность и её перестановки:");
while {
| |||