Работая Backend разработчиком в самой лучшей компании в мире, я столкнулся (или хотел столкнутся) c задачами, которые очень похожи на те, которые бывают в олимпиадном программировании. Именно о них и пойдет речь. Это первая часть статьи, в которой приведу одну задачу с подробным объяснением. Если вам также интересны алгоритмы и структуры данных, то прошу под кат!
Задача 1.
Дано: список уникальных объектов (для простоты возьмем числа), которые имеют закономерность в порядке следования.
Ограничения:
Необходимо перемешать элементы списка, чтобы ни один элемент списка не стоял на прежнем месте, а также чтобы закономерность в порядке следования нарушилась, то есть просто циклически сдвинуть элементы вправо или влево недостаточно.
Решение:
Пусть количество элементов в списке — n. Так как, нам надо гарантировать, чтобы каждый элемент не стоял на прежнем месте, то мы будем для каждого элемента с индексом i, который изменяется от (n-1) до 1, генерировать случайное число — индекс от 0 до i не включительно. Таким образом, получив случайный индекс j, который не равен текущему индексу i, поменяем местами элементы, стоящие на i и j позициях.
Например:
Наш список = [1,7,5,2,6].
Заполним трассировочную таблицу для лучшей наглядности алгоритма, где i переобозначили через rightIndex, а j — leftIndex.
Выпишем начальный список и список, который получился в результате выполнения алгоритма.
[1,7,5,2,6]
[6,2,1,5,7]
Как мы видим, все элементы переместились на разные места, и нет ни одного элемента, который остался на своем месте. Если вы заметили, то rightIndex всегда меняется от последнего индекса списка до 1. А leftIndex генерируется случайно таким образом, чтобы он был строго меньше, соответствующего ему на каждой итерации цикла, rightIndex. За счет этого свойства и достигается конечный результат.
Напишем вышеприведенный метод на языке С#. Параметризуем его, чтобы можно было использовать для любых объектов (числа, строки, пользовательские типы данных).
Эту функцию я выложил в своем репозитории. Cсылка на GitHub здесь.
Если вы не согласны с правильностью работы алгоритма или не до конца поняли, то напишите в комментариях, я обязательно вам отвечу.
Если у вас есть более быстрое решение, или более простое (естественно объяснив и естественно с такими ограничениями), то прошу указать в комментариях, буду благодарен.
Задача 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 здесь.
Если вы не согласны с правильностью работы алгоритма или не до конца поняли, то напишите в комментариях, я обязательно вам отвечу.
Если у вас есть более быстрое решение, или более простое (естественно объяснив и естественно с такими ограничениями), то прошу указать в комментариях, буду благодарен.
Only registered users can participate in poll. Log in, please.
Вторая часть данного будет посвящена неточному поиску объектов. Интересно ли вам будет?
72.58% Да, конечно. Поскорее выкладывай.45
27.42% Нет, все и так понятно.17
62 users voted. 23 users abstained.