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



Олимпиадные задачи в промышленном программировании. Часть 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 здесь.

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

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

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (37):

  1. Sdima1357
    /#10512160

    которые имеют закономерность в порядке следования.

    До:
    массив int x[] = { 1 2 3 4 5 6 7 8 }
    закономерность x[n+1] = 2*x[n]-x[n-1];

    После например:
    x[] = {8 7 6 5 4 3 2 1 }
    закономерность x[n+1] = 2*x[n]-x[n-1];
    Ну надо же :)
    Выражайтесь корректнее пожалуйста.

  2. sidristij
    /#10512238

    10^5 элементов IList?

    • sidristij
      /#10512256

      Хотя не так и много, наверное… полметра… ок :)

  3. koldyr
    /#10512296

    Монтекарло это, безусловно, прекрасно, но может иметь весьма неожиданные последствия.
    Например: для n-1 выпало n-2, для n-2 выпало n-3 и так далее для 1 выпал очевидно 0
    получите подстановку (n-1,0,1,2,3,..,n-3,n-2), что противоречит условию задачи.
    Вам нужна функция без неподвижной точки, обладающая некоторым свойством «перемешивания». Если n «мало» то можно подогнать. Зафиксируйте генератор псевдослучайных чисел и его начальное состояние.

  4. Sdima1357
    /#10512442

    Несколько замечаний
    1 структура данных «список» ( смотрите википедию ) в общем случае не имеет быстрого доступа по индексу ( спасибо Microsoft за путаницу с IList в котором доступ по индексу в О(1) в документации не упомянут, хотя скорее всего реализован ) та структура данных что Автор имеет в виду называется «массив» у которого гарантирован доступ к элементу по индексу О(1)
    2 На самом деле это очень забавная задача, у которой корректная формулировка условия намного более нетривиальна чем ее решение — к примеру Автор однозначно не справился с формулировкой условия задачи. В определенном смысле приведённое автором решение и является минимальным описанием задачи, поэтому для олимпиады она ну никак не подходит.
    3 На практике- именно таким образом все программисты массивы и перемешивают, если хотят хорошо помешать карты например.
    Вообщем алгоритм +( ну он очень школьный ), а статья -

    • dimaaan
      /#10513346

      спасибо Microsoft за путаницу с IList в котором доступ по индексу в О(1) в документации не упомянут, хотя скорее всего реализован

      скорее всего реализован?
      IList — это интерфейс. Он не содержит реализации, поэтому в документации ничего не сказано про это. Так что не надо Microsoft зря ругать :)
      Если мы хотим гарантий — надо использовать конкретную структуру данных.
      Если хотим универсальности — через интерфейс.
      Автор выбрал второй путь.

      • Sdima1357
        /#10513430

        IList — это интерфейс

        Вы правы, не пишу на С шарпе. Однако не стоит называть массив — списком.
        Сравните с std::list из с++

  5. samsergey
    /#10512456

    Хорошая задачка, приходилось её решать. Приведённое решение неплохо справляется с задачей, но всё становится хитрее, если элементы повторяются, как например, буквы в реальном тексте. В таком, более общем виде, эта задача хорошо разобрана на Rosetta code. Там приводится и моё решение для Haskell, решающее задачу с фиксированным объёмом используемой памяти и за линейное время (в on-line режиме).

    • Sdima1357
      /#10512464

      Аналогично и на RosettaCode

      Shuffle the characters of a string in such a way that as many of the character values are in a different position as possible.
      задача сформулирована интуитивно понятно, однако некорректно

      • samsergey
        /#10512468

        Там есть элементарная метрика, которую можно минимизировать. Но, вы правы, для более точной постановки задачи следовало бы использовать какую-либо дистанцию между строками. Но в таком случае решение задачки потребует строгого доказательства, тестирования будет недостаточно.

        • askv
          /#10512582

          Не очень понятно, где на практике нужно решение такой задачи.

          • JosefDzeranov
            /#10513536

            Сори. Не могу рассказать)

            • JekaMas
              /#10513878

              Напомнило: однажды собеседовался в один проект СколТеха и мне дали задачу "реалезуйте цепь Маркова второго рода, скормите ей текст и сгенерируйте новый с ее помощью, покройте все тестами и красивыми интерфейсами".
              Сам удивился, но сделал.
              После стал расспрашивать о том, что же за космические задачи надо решать, коль такие вещи сходу спрашиваете? Оказалось, что все то же "сторонние api интегрировать".
              Но все очень серьезно...

  6. Dr_Dash
    /#10512550

    list<T>::iterator I1 = list.begin();
    list<T>::iterator I2 = list.begin();
    I2++;
    list<T>::iterator Istop = list.end();
    
    
    while(I2 < Istop)
    {
    list.swap(I1, I2);
    I1++; I1++;
    I2++; I2++;
    }
    // Если количество элементов нечётное, меняем последний с первым
    if(I1 < Istop)
    {
    list<T>::iterator I2 = list.begin();
    list.swap(I1, I2);
    }
    

    в результате ни один элемент не останется на прежнем месте, да и закономерность будет нарушена. То что закономерность сохранится через 1 элемент — не противоречит условию задачи, там не сказано насколько должна быть нарушена закономерность. А может просто «развернуть» список концом вперёд и тогда закономерность снова не останется прежней, более того, она инвертируется? Задача недоформулирована, как будто подразумевается что речь пойдёт о перемешивании методом Монте-Карло, и студент выберет это решение как само собой разумеющееся. Для олимпиадной задачи эта очень куцая.

  7. michael_vostrikov
    /#10512660 / +1

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

    • Sdima1357
      /#10512770

      Я использовал подобное перемешивание в итеративном восстановлении изображений из их проекций(медицинская томография КТ, скан спиральный, изображение 3D volume ). Позволяет избежать (уменьшить )образования паттернов на результирующей картинке при заведомо неизвестном (каждый скан разное ) числе проекций. Любая регулярная выборка образует паттерны

  8. HEKOT
    /#10512734

    Работая Backend разработчиком в самой лучшей компании в мире, я столкнулся (или хотел столкнутся) c задачами, которые очень похожи на те, которые бывают в олимпиадном программировании. Именно о них и пойдет речь. Это первая часть статьи, в которой приведу одну задачу с подробным объяснением.

    Задачка-то не на олимпиадный уровень. По-моему, с этого начинают изучать алгоритмы.

    Если вам также интересны алгоритмы и структуры данных, то

    читайте Вирта. Для желающихся подвинуться — Кнута.

    • Sdima1357
      /#10512794

      3-Томник Кнута, для желающих хорошо подвинуться

      • HEKOT
        /#10513156

        Строго говоря, 5-томник

        • Sdima1357
          /#10513162

          Я уже на трех подвинулся, а Вы про 5 :) (У меня трехтомник )

  9. genew
    /#10512790

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

  10. koldyr
    /#10512806

    Пронумеруем элементы от 1 до n.
    Пусть p>1 и (p,n) =1.
    i'=i*p mod n.
    Как-то так. Есть более извращенные идеи на этой основе, но думаю в данном случае это не нужно.

    • koldyr
      /#10513958

      Накосячил, раз считаем с 1 до n то модуль надо взять n+1 и, соответственно, (p,n+1)=1.

      • koldyr
        /#10513984

        Извините за недостатки, еще необходимо чтобы (p-1,n+1)=1. а значит, если n+1 четно, то ничего не выйдет.

  11. lair
    /#10513056

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

    Мне вот тоже не понятно это требование. Предположим, что циклический сдвиг недостаточен. Но предложенное решение, будучи вероятностным, способно дать в результате циклический сдвиг — значит, оно некорректно.


    При этом, скажем, есть тривиальное решение (для последовательности из более чем 3 элементов, все элементы уникальны), при котором последовательность просто разворачивается из конца в начало (если число элементов нечетное, средний элемент сначала обменивается с первым). Ни один из элементов не остается на своем месте, закономерность нарушена, вычислительная сложность O(n). Что я делают не так?


    int maxIndex = list.Count - 1;
    for (int i = 0; i < maxIndex; i++)
    {
    int rightIndex = maxIndex - i;

    А зачем так сложно, почему нельзя сразу написать for (var rightIndex = list.Count-1; rightIndex >= 1; rightIndex--)?

  12. Zadolballi
    /#10513538

    > Работая Backend разработчиком в самой лучшей компании в мире

    Собственно, я зашёл сюда поинтересоваться: какая компания является лучшей в мире? И по каким критериям. Спасибо.

  13. evgenicx
    /#10513542

    Легко можно найти закономерность, особенно на малом количестве элементов. Поэтому действительно не очень понятно что под этим имеется ввиду.
    И второй вопрос — что это за самая лучшая компания в мире?)

  14. shockable
    /#10513544

    Немного похоже на www.rosettacode.org/wiki/Knuth_shuffle

  15. evkochurov
    /#10513554

    Можно вдвое уменьшить количество обменов и генераций случайных чисел, если в цикле пропускать элементы, которые уже поменяли свое положение. Правда, не знаю, насколько полно это решение удовлетворяет требованиям:
    — придется завести битовую карту размером до 12Кб;
    — степень перемешивания будет похуже, хотя, формально, исходная закономерность нарушится и никто не останется на том же месте.

    • JosefDzeranov
      /#10513556

      Да, хорошее олимпиадное решение. Мне понравилось

  16. tobolenok
    /#10513558

    *или хотел столкнуться