Задача 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)
koldyr
08.11.2017 23:20Монтекарло это, безусловно, прекрасно, но может иметь весьма неожиданные последствия.
Например: для n-1 выпало n-2, для n-2 выпало n-3 и так далее для 1 выпал очевидно 0
получите подстановку (n-1,0,1,2,3,..,n-3,n-2), что противоречит условию задачи.
Вам нужна функция без неподвижной точки, обладающая некоторым свойством «перемешивания». Если n «мало» то можно подогнать. Зафиксируйте генератор псевдослучайных чисел и его начальное состояние.
Sdima1357
09.11.2017 01:26Несколько замечаний
1 структура данных «список» ( смотрите википедию ) в общем случае не имеет быстрого доступа по индексу ( спасибо Microsoft за путаницу с IList в котором доступ по индексу в О(1) в документации не упомянут, хотя скорее всего реализован ) та структура данных что Автор имеет в виду называется «массив» у которого гарантирован доступ к элементу по индексу О(1)
2 На самом деле это очень забавная задача, у которой корректная формулировка условия намного более нетривиальна чем ее решение — к примеру Автор однозначно не справился с формулировкой условия задачи. В определенном смысле приведённое автором решение и является минимальным описанием задачи, поэтому для олимпиады она ну никак не подходит.
3 На практике- именно таким образом все программисты массивы и перемешивают, если хотят хорошо помешать карты например.
Вообщем алгоритм +( ну он очень школьный ), а статья -
dimaaan
09.11.2017 15:05спасибо Microsoft за путаницу с IList в котором доступ по индексу в О(1) в документации не упомянут, хотя скорее всего реализован
скорее всего реализован?
IList — это интерфейс. Он не содержит реализации, поэтому в документации ничего не сказано про это. Так что не надо Microsoft зря ругать :)
Если мы хотим гарантий — надо использовать конкретную структуру данных.
Если хотим универсальности — через интерфейс.
Автор выбрал второй путь.Sdima1357
09.11.2017 15:54IList — это интерфейс
Вы правы, не пишу на С шарпе. Однако не стоит называть массив — списком.
Сравните с std::list из с++
samsergey
09.11.2017 01:54Хорошая задачка, приходилось её решать. Приведённое решение неплохо справляется с задачей, но всё становится хитрее, если элементы повторяются, как например, буквы в реальном тексте. В таком, более общем виде, эта задача хорошо разобрана на Rosetta code. Там приводится и моё решение для Haskell, решающее задачу с фиксированным объёмом используемой памяти и за линейное время (в on-line режиме).
Sdima1357
09.11.2017 02:02Аналогично и на 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
09.11.2017 02:16Там есть элементарная метрика, которую можно минимизировать. Но, вы правы, для более точной постановки задачи следовало бы использовать какую-либо дистанцию между строками. Но в таком случае решение задачки потребует строгого доказательства, тестирования будет недостаточно.
askv
09.11.2017 08:05Не очень понятно, где на практике нужно решение такой задачи.
JosefDzeranov Автор
09.11.2017 16:53Сори. Не могу рассказать)
JekaMas
09.11.2017 20:40Напомнило: однажды собеседовался в один проект СколТеха и мне дали задачу "реалезуйте цепь Маркова второго рода, скормите ей текст и сгенерируйте новый с ее помощью, покройте все тестами и красивыми интерфейсами".
Сам удивился, но сделал.
После стал расспрашивать о том, что же за космические задачи надо решать, коль такие вещи сходу спрашиваете? Оказалось, что все то же "сторонние api интегрировать".
Но все очень серьезно...
Dr_Dash
09.11.2017 07:14list<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 элемент — не противоречит условию задачи, там не сказано насколько должна быть нарушена закономерность. А может просто «развернуть» список концом вперёд и тогда закономерность снова не останется прежней, более того, она инвертируется? Задача недоформулирована, как будто подразумевается что речь пойдёт о перемешивании методом Монте-Карло, и студент выберет это решение как само собой разумеющееся. Для олимпиадной задачи эта очень куцая.
michael_vostrikov
09.11.2017 09:12+1По названию ожидал описание реальных задач. Подскажите кто-нибудь пару примеров, где это применяется.
Sdima1357
09.11.2017 10:24Я использовал подобное перемешивание в итеративном восстановлении изображений из их проекций(медицинская томография КТ, скан спиральный, изображение 3D volume ). Позволяет избежать (уменьшить )образования паттернов на результирующей картинке при заведомо неизвестном (каждый скан разное ) числе проекций. Любая регулярная выборка образует паттерны
HEKOT
09.11.2017 10:00Работая Backend разработчиком в самой лучшей компании в мире, я столкнулся (или хотел столкнутся) c задачами, которые очень похожи на те, которые бывают в олимпиадном программировании. Именно о них и пойдет речь. Это первая часть статьи, в которой приведу одну задачу с подробным объяснением.
Задачка-то не на олимпиадный уровень. По-моему, с этого начинают изучать алгоритмы.
Если вам также интересны алгоритмы и структуры данных, то
читайте Вирта. Для желающихся подвинуться — Кнута.
genew
09.11.2017 10:42Если речь про промышленное программирование, то наверное стоило привести пример, для чего может понадобиться решать такую задачу?
koldyr
09.11.2017 10:49Пронумеруем элементы от 1 до n.
Пусть p>1 и (p,n) =1.
i'=i*p mod n.
Как-то так. Есть более извращенные идеи на этой основе, но думаю в данном случае это не нужно.
lair
09.11.2017 12:39Необходимо перемешать элементы списка, чтобы ни один элемент списка не стоял на прежнем месте, а также чтобы закономерность в порядке следования нарушилась, то есть просто циклически сдвинуть элементы вправо или влево недостаточно.
Мне вот тоже не понятно это требование. Предположим, что циклический сдвиг недостаточен. Но предложенное решение, будучи вероятностным, способно дать в результате циклический сдвиг — значит, оно некорректно.
При этом, скажем, есть тривиальное решение (для последовательности из более чем 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--)?
Zadolballi
09.11.2017 16:54> Работая Backend разработчиком в самой лучшей компании в мире
Собственно, я зашёл сюда поинтересоваться: какая компания является лучшей в мире? И по каким критериям. Спасибо.
evgenicx
09.11.2017 16:55Легко можно найти закономерность, особенно на малом количестве элементов. Поэтому действительно не очень понятно что под этим имеется ввиду.
И второй вопрос — что это за самая лучшая компания в мире?)
evkochurov
09.11.2017 16:57Можно вдвое уменьшить количество обменов и генераций случайных чисел, если в цикле пропускать элементы, которые уже поменяли свое положение. Правда, не знаю, насколько полно это решение удовлетворяет требованиям:
— придется завести битовую карту размером до 12Кб;
— степень перемешивания будет похуже, хотя, формально, исходная закономерность нарушится и никто не останется на том же месте.
Sdima1357
До:
массив 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];
Ну надо же :)
Выражайтесь корректнее пожалуйста.