Реализации алгоритмов/Алгоритм Нарайаны: различия между версиями
Содержимое удалено Содержимое добавлено
Поправки к коду реализаций |
Добавлена реализация на Java и пример её использования |
||
Строка 201:
delete [] sequence;
return 0;
}
</source>
==[[w:Java|Java]]==
<source lang="java">
// Narayana.java
abstract class Narayana {
@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) {
// Этап № 1
int j = sequence.length, i = j - 1;
do {
if (j < 2)
return false;
} while (!comparator.compare(sequence[--i], sequence[--j]));
// Этап № 2
j = sequence.length;
while (i < j && !comparator.compare(sequence[i], sequence[--j]));
_swapItems(sequence, i, j);
// Этап № 3
j = sequence.length;
while (++i < j && i < --j)
_swapItems(sequence, i, j);
return true;
}
}
</source>
Пример использования:
<source lang="java">
// 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) {
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 — критерий сравнения для невозрастающей последовательности
}
}
</source>
| |||