Произвольно переставить N первых элементов односвязного списка

Question

Я должен случайным образом переставить N первых элементов односвязного списка длины n. Каждый элемент определяется как:

typedef struct E_s
{
  struct E_s *next;
}E_t;

У меня есть корневой элемент, и я могу просмотреть весь связанный список размером n. Какой метод наиболее эффективен для случайной перестановки только N первых элементов (начиная с корня)?

Итак, учитывая a-> b-> c-> d-> e-> f-> ... x-> y-> z, мне нужно сделать что-то. как f-> a-> e-> c-> b -> ... x-> y-> z

Мой конкретный случай:

• n-N составляет около 20% относительно n
• У меня ограниченные ресурсы оперативной памяти, лучший алгоритм должен сделать это на месте
• Я должен сделать это в цикле, во многих итерациях, поэтому скорость имеет значение
• Идеальная случайность (равномерное распределение) не требуется, это нормально, если она "почти" случайна
• Прежде чем делать перестановки, я уже пересекаю N элементов (для других нужд), поэтому, возможно, я мог бы использовать это и для перестановок

ОБНОВЛЕНИЕ: я нашел этот документ . Это заявляет, что представляет алгоритм O (log n) стекового пространства и ожидаемого O (n log n) времени.

Answer 1

Аналогично ответу Влада, здесь есть небольшое улучшение (статистически):

Индексы в алгоритме основаны на 1.

1. Инициализировать lastR = -1
2. Если N <= 1, переходите к шагу 6. ​​</li>
3. Произведите случайное число r между 1 и N.

4. , если r! = N

   4.1.r и его предшественник.

   If lastR != -1
   If r == lastR, your pointer for the of the r'th item predecessor is still there.
   If r < lastR, traverse to it from the beginning of the list.
   If r > lastR, traverse to it from the predecessor of the lastR'th item.
   

   4.2 удалить r-й элемент из списка в список результатов в качестве хвоста.

   4.3 lastR = r

5. Уменьшите N на единицу и перейдите к шагу 2.
6. свяжите хвост списка результатов с заголовком оставшегося списка ввода.Теперь у вас есть исходный список с перестановкой первых N элементов.

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