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

Перейти к навигации Перейти к поиску
Нет описания правки
(Добавлена реализация и пример её использования на основе C++11)
Алгоритм поиска очередной перестановки для последовательности с неубывающим (невозрастающим) '''изначальным''' порядком элементов:
# Найти наибольшее <math>i</math>, для которого выполняется условие <math>sequence_{i} < sequence_{i+1}</math> (<math>sequence_{i} > sequence_{i+1}</math>). Если такого нет, значит все перестановки были сгенерированы.
# Найти наибольшее <math>j>i</math>, для которого выполняется условие <math>sequence_{i} < sequence_{j}</math> (<math>sequence_{i} > sequence_{j}</math>). Затем поменять местами <math>sequence_{i}</math> и <math>sequence_{j}</math>.
# Элементы <math>sequence_{i+1}, ..., sequence_{count}</math> переставить в обратном порядке.
 
В нижеприведённых реализациях <code>sequence</code> — последовательность из <code>count</code> элементов, в которой производятся перестановки (как правило — массив из count элементов), <code>compare(x, y)</code> — функция, которая должна возвращать <code>true</code> если x < y и <code>false</code> иначе (если исходный порядок элементов последовательности неубывающий; для невозрастающего исходного порядка условие меняется на x > y).
 
Если не оговорено другое, то функция поиска очередной перестановки возвращает ненулевое значение «истина», если перестановка найдена, либо 0«ложь», если следующей перестановки не существует (перебор закончен).
 
==[[w:C (язык программирования)|C]]==
do {
if (i < 2)
return 0; /* Перебор закончен */
--i;
} while (!(*compare)(sequence[i - 1], sequence[i]));
for (j = i + 1; j <= (count + i) >> 1; ++j) /* >> 1 — более быстрый вариант / 2 */
_swapItems(sequence, j, count + i - j);
return j1;
}
</source>
#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;
}
 
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;
 
{ Поиск очередной перестановки }
function NextPermutation (var sequence: array of T; Compare: TPredicate2): WordBoolean;
var count, i, j: Word;
{ Обмен значениями двух элементов последовательности }
if i < 2 then
begin
NextPermutation := 0false;
Exit
end;
for j := i + 1 to (count + i) shr 1 do { shr 1 — более быстрый вариант div 2 }
SwapItems(j, count + i - j);
NextPermutation := jtrue
end;
 
repeat
OutputSequence(sequence)
until not NextPermutation(sequence, @Less) = 0; { x < y — критерий сравнения для неубывающей последовательности }
WriteLn;
WriteLn('Невозрастающая последовательность и её перестановки:');
repeat
OutputSequence(sequence)
until not NextPermutation(sequence, @Greater) = 0 { x > y — критерий сравнения для невозрастающей последовательности }
END.
</source>
// narayana.rs
// Поиск очередной перестановки
fn next_permutation <T: Copy + PartialOrd> (sequence: &mut[T], compare: fn (T, T) -> bool) -> usizebool {
let count = sequence.len();
let mut i = count;
loop {
if i < 2 {
return 0false;
}
i -= 1;
j += 1;
}
jtrue
}
</source>
while {
println!("{:?}", sequence);
narayana::next_permutation(&mut sequence, less::<usize>) > 0 // x < y — критерий сравнения для неубывающей последовательности
} { }
println!("");
while {
println!("{:?}", sequence);
narayana::next_permutation(&mut sequence, greater::<usize>) > 0 // x > y — критерий сравнения для невозрастающей последовательности
} { }
}
74

правки

Навигация