Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Добавлены реализации на VB.NET, Python и примеры их использования; скорректировано оформление программ на других языках
Добавлена реализация и пример её использования на C#; подкорректированы остальные языки
Строка 19:
<source lang="vb">
' 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) (ByRefByVal sequence As T(), ByVal compare As Predicate2(Of T)) As Boolean
' Этап № 1
Dim i As Integer = sequence.Length
Строка 40:
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
Строка 54:
''' Обмен значениями двух элементов последовательности
''' </summary>
Private Sub _SwapItems (Of T) (ByRefByVal 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)
Строка 68:
''' Возвращает True, если value_0 меньше value_1, иначе — False
''' </summary>
Private Function Less (Of T As IComparable) (ByVal value_0 As IntegerT, ByVal value_1 As IntegerT) As Boolean
Return value_0.CompareTo(value_1) < 0
End Function
Строка 75:
''' Возвращает True, если value_0 больше value_1, иначе — False
''' </summary>
Private Function Greater (Of T As IComparable) (ByVal value_0 As IntegerT, ByVal value_1 As IntegerT) As Boolean
Return value_0.CompareTo(value_1) > 0
End Function
Строка 82:
''' Инициализация последовательности
''' </summary>
Private Sub InitSequence (ByRefByVal sequence As Integer())
' Заполнение последовательности значениями 1, 2, 3…
For i As Integer = sequence.Length To 1 Step -1
sequence(i - 1) = i
Строка 91 ⟶ 92 :
''' Вывод содержимого последовательности
''' </summary>
Private Sub OutputSequence (Of T) (ByVal sequence As T())
Console.Write("["C)
If sequence IsNot Nothing And sequence.Length > 0 Then
Строка 106 ⟶ 107 :
''' Основная программа
''' </summary>
Public Sub Main (ByVal args As String())
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)) ' x < y — критерий сравнения для неубывающей последовательности
Console.WriteLine("Невозрастающая последовательность и её перестановки:")
Do
OutputSequence(Of Integer)(sequence)
Loop While Narayana.NextPermutation(sequence, AddressOf Greater(Of Integer)) ' x > y — критерий сравнения для невозрастающей последовательности
End Sub
End Module
Строка 155 ⟶ 156 :
} 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;
Строка 283 ⟶ 284 :
template < typename Iterator >
void initSequence (Iterator const begin, Iterator const end) {
// Заполнение последовательности значениями 1, 2, 3…
int i = 0;
for (Iterator current = begin; current != end; ++current)
Строка 315 ⟶ 317 :
delete [] sequence;
return 0;
}
</source>
 
==[[w:C_Sharp|C#]]==
<source lang="csharp">
// 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;
}
}
</source>
Пример использования:
<source lang="csharp">
// 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 — критерий сравнения для невозрастающей последовательности
}
}
</source>
Строка 343 ⟶ 460 :
// Этап № 3
j = sequence.length;
while (i < j && i < --j)
_swapItems(sequence, i++, j);
return true;
Строка 376 ⟶ 493 :
// Инициализация последовательности
static final void initSequence (Integer[] sequence) {
// Заполнение последовательности значениями 1, 2, 3…
for (int value = sequence.length; value > 0; --value)
sequence[value - 1] = value;
Строка 445 ⟶ 563 :
{ Этап № 3 }
j := count;
while (i < j) and (i < j - 1) do
begin
j := j - 1;
Строка 600 ⟶ 718 :
# Этап № 3
j = count
while i < j and i < j - 1:
j -= 1
sequence[i], sequence[j] = sequence[j], sequence[i]
Строка 622 ⟶ 740 :
# Основная программа
count = int(input());
sequence = list(range(1, count + 1)) # Формирование исходнойЗаполнение последовательности значениями 1, 2, 3…
print("Неубывающая последовательность и её перестановки:")
while True:
Строка 658 ⟶ 776 :
// Этап № 3
j = count;
while i < j && i < j - 1 {
j -= 1;
sequence.swap(i, j);
Строка 680 ⟶ 798 :
 
// Инициализация последовательности
fn init_sequence (sequence: &mut [usizei32]) {
// Заполнение последовательности значениями 1, 2, 3…
let mut i = sequence.len();
let mut value = i as i32;
while i > 0 {
sequence[i - 1] = i;
i -= 1;
sequence[i] = value;
value -= 1;
}
}
Строка 705 ⟶ 825 :
let mut count = 0usize;
read_var(&mut count);
let mut sequence = vec![0usize0i32; count];
init_sequence(&mut sequence); // Формирование исходной последовательности
println!("Неубывающая последовательность и её перестановки:");
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Алгоритм_Нарайаны