C++. Алгоритмы STL

lower_bound и upper_bound - встроенные функции бинарного поиска.

lower_bound - функция, которая за логарифмическое время в отсортированном массиве находит наименьший элемент, который больше заданного значения k или равен ему.
В качестве аргументов принимает границы массива и значение k.
Возвращает итератор на найденный элемент или на конец (невключенный) массива, если такого элемента не существует.
Подробнее можете прочитать в документации.

upper_bound - функция, которая за логарифмическое время в отсортированном массиве находит наименьший элемент, который строго больше заданного значения k.
В качестве аргументов принимает границы массива и значение k.
Возвращает итератор на найденный элемент или на конец (невключенный) массива, если такого элемента не существует.
Подробнее можете прочитать в документации.

Стоит уточнить, что применение данных функций на set или multiset работает не за логарифмическое время по причине отсутствия у вышеупомянутых коллекций random access итераторов.
Однако у этих коллекций есть соответствующие встроенные методы (то есть нужно использовать их "через точку").

Примеры:
 

	vector a = { 0, 1, 3, 5, 7 };
	vector::iterator it;
	
	it = lower_bound(a.begin(), a.end(), 4);
	// *it == 5

	it = lower_bound(a.begin(), a.end(), 5);
	// *it == 5

	it = lower_bound(a.begin(), a.end(), 8);
	// it == a.end()
	
	it = upper_bound(a.begin(), a.end(), 4);
	// *it == 5

	it = upper_bound(a.begin(), a.end(), 5);
	// *it == 7

	it = upper_bound(a.begin(), a.end(), -1);
	// *it == 0


	// путем вычета итераторов можно получить индекс найденного элемента
	int ind = lower_bound(a.begin(), a.end(), 4) - a.begin();
	// ind == 3


	// нужно использовать методы вместо функций для set и аналогичных коллекций

	set s{ 1, 3, 5 };
	set::iterator sit;

	sit = s.lower_bound(3);
	// *sit == 3

	sit = s.upper_bound(3);
	// *sit == 5

 

unique - функция, которая за линейное время сжимает все последовательности одинаковых подряд идущих элементов в один.
В качестве аргумента ей передаются границы массива, в пределах которых необходимо применить сжатие.
Возвращается же итератор на новый конец (не включительно) массива. Стоит быть внимательным с элементами, расположенными после нового конца, но до старого, так как они будут иметь неопределенное значение.
Подробнее можете прочитать в документации.

Если вы применяете эту функцию на vector, то удобно делать resize, используя возвращаемый результат (подробнее ниже).

Примеры:
 

	vector  a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 };
	unique(a.begin(), a.end());
	// a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?]


	// с помощью функции unique удобно делать
	// вспомогательный массив для сжатия координат

	a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 };
	sort(a.begin(), a.end());
	// a = [10, 10, 41, 41, 41, 235, 235, 500, 500]

	a.resize(unique(a.begin(), a.end()) - a.begin());
	// a = [10, 41, 235, 500]

 

merge - функция, которая объединяет два отсортированных массива, а именно, за линейное время получает отсортированный массив, который состоит из элементов первого и второго массива.
Она принимает 5 аргументов: по две границы для каждого массива и левая граница места назначения (где будут расположены элементы результирующего массива).
Подробнее можете ознакомиться в документации.

Примеры:

	// исходные массивы должны быть отсортированы
	vector a = { 1, 3, 5, 7 };
	vector b = { 2, 4, 6 };

	// необходимо, чтобы место назначения имело достаточный размер
	vector c(7); 
	
	merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
	// c = [1, 2, 3, 4, 5, 6, 7]


	// элементы могут повторяться
	a = { 1, 2, 4, 4};
	b = { 2, 3, 3, 3, 4, 4 };
	c.resize(10);

	merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
	// c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

 Данную функцию очень удобно использовать в контексте сортировки слиянием.

nth_element - функция, которая позволяет находить n-ый элемент в массиве в отсортированном порядке за линейное время.
Функция принимает левую границу массива, итератор на позицию, значение которой в отсортированном порядке необходимо найти и правую границу массива.
После применения функции на указанном по итератору месте будет находиться необходимое значение, при этом остальные значения приобретут хаотичный порядок, но левее n-ого будут значения не больше его, а правее не меньше. То есть стоит понимать, что эта функция рушит исходный порядок элементов.
Подробнее можете прочитать в документации (https://www.cplusplus.com/reference/algorithm/nth_element/).

Пример:

	vector a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 };
	
	// ищем элемент по индексу 4
	// обратите внимание на порядок аргументов
	nth_element(a.begin(), a.begin() + 4, a.end());
	// a = [#, #, #, #, 4, $, $, $, $, $]
	// где # <= 4 и 4 <= $

 

Перебор всех перестановок

 

Перестановка, о которой мы здесь поговорим, заключается в том, как расположить n объектов в n позициях. Причем, в перестановке важен порядок элементов.

Как перечислить все перестановки?
Начнем с наименьшего числа (с 1) и далее будем получать все остальные перестановки из оставшихся чисел. Потом возьмем следующее после минимального и опять будем отавлять перестановки из оставшихся чисел по такому же принципу. 
Например, нам необходимо перебрать все перестановки длиной 3 из первых трех букв английского алфавита.  По описанному выше принципу перечисления перестановок, выглядеть список будет таким образом:
ABC
ACB 
BAC 
BCA 
CAB
CBA

Всего перестановк из трех элементов 6.
Для n объектов количество перестановок равно Pn = n!.

Рассмотрим другой полезный подход к решению задачи перебора. Идея заключается в том, чтобы создать глобальный массив, назовем его used, который будет содержать информацию о том, использовали ли мы каждое число или нет. Когда мы рассматриваем очередной элемент для добавления в перестановку, мы проверяем значение в used для этого элемента. Если оно равно false, то это значит, что число ещё не использовалось, и мы можем включить его в перестановку. Затем мы помечаем этот элемент как использованный, устанавливая соответствующий флаг в used на значение true.

Таким образом, мы гарантируем, что каждое число будет использовано только один раз в перестановке, и избегаем повторений.

Запишем алгоритм на псевдокоде

алгоритм generate(n, used, pref)
    если длина(pref) = n то
        check(pref) 
    иначе
        для каждого next от 1 до n выполнить
            если not used[next] то
                used[next] = True
                generate(n, used, pref + [next])
                used[next] = False
            конец если
        конец цикла
    конец если
конец алгоритма

В программе выше используется алгоритм generate, который принимает три параметра: n (максимальное число в перестановке), used (массив, отслеживающий использованные каждого числа) и pref (текущий префикс перестановки).  Если префикс имеет длину n, значит мы добавили в перестановку все числа. Вызываем процедуру check  для обработки перестановки.
Иначе, для каждого числа next от 1 до n (включительно), мы проверяем, было ли число использовано ранее (проверка not used[next]). Если число не использовалось, помечаем его как использованное (used[next] = True), рекурсивно вызываем алгоритм generate с обновленными значениями used и pref, и затем освобождаем число для следующей ветки (следующей перестановки), помечая его как неиспользованное (used[next] = False).

Реализуйте данный алгоритм на знакомом вам языке программирования!