Олимпиадные задачи в промышленном программировании. Часть 1 -1


Работая 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 здесь.

Если вы не согласны с правильностью работы алгоритма или не до конца поняли, то напишите в комментариях, я обязательно вам отвечу.

Если у вас есть более быстрое решение, или более простое (естественно объяснив и естественно с такими ограничениями), то прошу указать в комментариях, буду благодарен.




К сожалению, не доступен сервер mySQL