Работая Backend разработчиком в самой лучшей компании в мире, я столкнулся (или хотел столкнутся) c задачами, которые очень похожи на те, которые бывают в олимпиадном программировании. Именно о них и пойдет речь. Это первая часть статьи, в которой приведу одну задачу с подробным объяснением.
Задача 1.
Дано: список уникальных объектов (для простоты возьмем числа), которые имеют закономерность в порядке следования.
Ограничения:
- количество элементов до 10^5;
- накладно создавать новый список, следовательно нужно изменить тот же список.
Необходимо перемешать элементы списка, чтобы ни один элемент списка не стоял на прежнем месте, а также чтобы закономерность в порядке следования нарушилась, то есть просто циклически сдвинуть элементы вправо или влево недостаточно.
Решение:
Пусть количество элементов в списке — n. Так как, нам надо гарантировать, чтобы каждый элемент не стоял на прежнем месте, то мы будем для каждого элемента с индексом i, который изменяется от (n-1) до 1, генерировать случайное число — индекс от 0 до i не включительно. Таким образом, получив случайный индекс j, который не равен текущему индексу i, поменяем местами элементы, стоящие на i и j позициях.
Например:
Наш список = [1,7,5,2,6].
Заполним трассировочную таблицу для лучшей наглядности алгоритма, где i переобозначили через rightIndex, а j — leftIndex.
rightIndex | leftIndex | List(список) | |
4 | 1 | [1,6,5,2,7] | |
3 | 2 | [1,6,2,5,7] | |
2 | 0 | [2,6,1,5,7] | |
1 | 0 | [6,2,1,5,7] |
Выпишем начальный список и список, который получился в результате выполнения алгоритма.
[1,7,5,2,6]
[6,2,1,5,7]
Как мы видим, все элементы переместились на разные места, и нет ни одного элемента, который остался на своем месте. Если вы заметили, то rightIndex всегда меняется от последнего индекса списка до 1. А leftIndex генерируется случайно таким образом, чтобы он был строго меньше, соответствующего ему на каждой итерации цикла, rightIndex. За счет этого свойства и достигается конечный результат.
Напишем вышеприведенный метод на языке С#. Параметризуем его, чтобы можно было использовать для любых объектов (числа, строки, пользовательские типы данных).
// Напишем метод расширения для удобства использования для параметризованного списка.
public static void Shiffle<T>(this IList<T> list)
{
var random = new Random();
int maxIndex = list.Count — 1;
for (int i = 0; i < maxIndex; i++)
{
int rightIndex = maxIndex — i;
int leftIndex = random.Next(0, rightIndex);
list.Swap(leftIndex, rightIndex);
}
}
// Меняем два элемента местами в списке с заданными индексами
public static void Swap<T>(this IList<T> list, int index1, int index2)
{
T c = list[index1];
list[index1] = list[index2];
list[index2] = c;
}
Эту функцию я выложил в своем репозитории. Cсылка на GitHub здесь.
Если вы не согласны с правильностью работы алгоритма или не до конца поняли, то напишите в комментариях, я обязательно вам отвечу.
Если у вас есть более быстрое решение, или более простое (естественно объяснив), то прошу указать в комментариях, буду благодарен.