Алгоритм перетасовки связанного списка за n log n раз

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

Алгоритм.

shuffle(list):
    if list contains a single element
        return list

    list1,list2 = [],[]
    while list not empty:
        move front element from list to list1
        if list not empty: move front element from list to list2

    shuffle(list1)
    shuffle(list2)

    if length(list2) < length(list1):
        i = pick a number uniformly at random in [0..length(list2)]             
        insert a dummy node into list2 at location i 

    # merge
    while list1 and list2 are not empty:
        if coin flip is Heads:
            move front element from list1 to list
        else:
            move front element from list2 to list

    if list1 not empty: append list1 to list
    if list2 not empty: append list2 to list

    remove the dummy node from list

Ключевым моментом для пространства является то, что разделение списка на два не требует дополнительного места. Единственное дополнительное пространство, которое нам нужно, — это поддерживать log n элементов в стеке во время рекурсии.

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

Анализ. Почему распределение равномерное? После окончательного слияния вероятность P_i(n) того, что любое заданное число окажется в позиции i, следующая. Либо это было:

• на i месте в своем списке, и список выиграл первый подбрасывание монеты i раз, вероятность этого 1/2^i;
• на i-1-м месте в своем списке, и список выиграл в подбрасывании монеты i-1 раз включая последний и проиграл один раз, вероятность этого (i-1) choose 1 раз 1/2^i;
• на i-2-м месте в своем списке, и список выиграл в подбрасывании монеты i-2 раз включая последний и дважды проиграл, вероятность этого (i-1) choose 2 раз 1/2^i;
• и так далее.

Таким образом, вероятность

P_i(n) = \sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * P_j(n/2).

Индуктивно можно показать, что P_i(n) = 1/n. Я позволю вам проверить базовый случай и предположить, что P_j(n/2) = 2/n. Термин \sum_{j=0}^{i-1} (i-1 choose j) — это точное количество i-1-битных двоичных чисел, то есть 2^{i-1}. Итак, мы получаем

P_i(n) = \sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * 2/n
       = 2/n * 1/2^i * \sum_{j=0}^{i-1} (i-1 choose j)
       = 1/n * 1/2^{i-1} * 2^{i-1}
       = 1/n

Я надеюсь это имеет смысл. Единственное предположение, которое нам нужно, это то, что n четно, и что два списка перетасованы равномерно. Это достигается добавлением (а затем удалением) фиктивного узла.

P.S. Моя первоначальная интуиция была далеко не строгой, но я привожу ее на всякий случай. Представьте, что мы случайным образом присваиваем числа от 1 до n элементам списка. И теперь мы запускаем сортировку слиянием по этим числам. На любом этапе слияния необходимо решить, какая из голов двух списков меньше. Но вероятность того, что одно больше другого, должна быть ровно 1/2, поэтому мы можем смоделировать это, подбрасывая монету.

П.П.С. Есть ли способ встроить LaTeX сюда?

Код

Подход с перетасовкой вверх

Эта (lua) версия улучшена по сравнению с ответом foxcub, чтобы устранить необходимость в фиктивных узлах.

Чтобы немного упростить код в этом ответе, в этой версии предполагается, что ваши списки знают свои размеры. В случае, если они этого не делают, вы всегда можете найти его за O(n) время, но даже лучше: можно сделать несколько простых изменений в коде, чтобы не требовать его вычисления заранее (например, разделить один на два вместо первой и второй половины). ).

function listUpShuffle (l)
    local lsz = #l
    if lsz <= 1 then return l end

    local lsz2 = math.floor(lsz/2)
    local l1, l2 = {}, {}
    for k = 1, lsz2     do l1[#l1+1] = l[k] end
    for k = lsz2+1, lsz do l2[#l2+1] = l[k] end

    l1 = listUpShuffle(l1)
    l2 = listUpShuffle(l2)

    local res = {}
    local i, j = 1, 1
    while i <= #l1 or j <= #l2 do
        local rem1, rem2 = #l1-i+1, #l2-j+1
        if math.random() < rem1/(rem1+rem2) then
            res[#res+1] = l1[i]
            i = i+1
        else
            res[#res+1] = l2[j]
            j = j+1
        end
    end
    return res
end

Чтобы избежать использования фиктивных узлов, вы должны компенсировать тот факт, что два промежуточных списка могут иметь разную длину, изменяя вероятность выбора в каждом списке. Это делается путем проверки равномерного случайного числа [0,1] на отношение количества узлов, извлеченных из первого списка, к общему количеству извлеченных узлов (в двух списках).

Перетасовка вниз

Вы также можете перетасовывать во время рекурсивного деления, что в моих скромных тестах показало немного (но неизменно) лучшую производительность. Это может произойти из-за меньшего количества инструкций или, с другой стороны, могло появиться из-за прогрева кеша в luajit, поэтому вам придется профилировать для ваших вариантов использования.

function listDownShuffle (l)
    local lsz = #l
    if lsz <= 1 then return l end

    local lsz2 = math.floor(lsz/2)
    local l1, l2 = {}, {}
    for i = 1, lsz do
        local rem1, rem2 = lsz2-#l1, lsz-lsz2-#l2
        if math.random() < rem1/(rem1+rem2) then
            l1[#l1+1] = l[i]
        else
            l2[#l2+1] = l[i]
        end
    end

    l1 = listDownShuffle(l1)
    l2 = listDownShuffle(l2)

    local res = {}
    for i = 1, #l1 do res[#res+1] = l1[i] end
    for i = 1, #l2 do res[#res+1] = l2[i] end
    return res
end

Тесты

Полный исходный код находится в моем listShuffle.lua Gist.

Он содержит код, который при выполнении печатает матрицу, представляющую для каждого элемента входного списка, сколько раз он появляется в каждой позиции выходного списка после заданного количества запусков. Достаточно однородная матрица «показывает» равномерность распределения символов, а значит, и равномерность перетасовки.

Вот пример запуска с 1000000 итераций с использованием (не степени двойки) списка из 3 элементов:

>> luajit listShuffle.lua 1000000 3
Up shuffle bias matrix:
333331 332782 333887
333377 333655 332968
333292 333563 333145
Down shuffle bias matrix:
333120 333521 333359
333435 333088 333477
333445 333391 333164

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

Определение. Предположим, у нас есть список L, содержащий элементы a1, a2 ... an и индексы 1, 2, 3..... n. Если мы подвергаем L операции перемешивания (к внутренним компонентам у нас нет доступа), L будет идеально перемешано тогда и только тогда, когда, зная индексы некоторых k (k< n) элементов, мы не сможем вывести индексы оставшихся n-k элементов. То есть оставшиеся n-k элементов с равной вероятностью обнаружатся по любому из оставшихся n-k индексов.

Пример: если у нас есть список из четырех элементов [a, b, c, d] и после его перетасовки мы знаем, что его первый элемент a ([a, .., .., ..]), то вероятность того, что любой из элементов b, c, d появится, скажем, в третьей ячейке, равна 1/3.

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

Рассмотрим ввод L = [a, b, c, d]После первого запуска алгоритма L будет разделен на l1 = [a, c] и l2 = [b, d]. После перетасовки этих двух подсписков (но перед объединением в четырехэлементный результат) мы можем получить четыре равновероятных двухэлементных списка:

l1shuffled = [a , c]     l2shuffled = [b , d]
l1shuffled = [a , c]     l2shuffled = [d , b]
l1shuffled = [c , a]     l2shuffled = [b , d]
l1shuffled = [c , a]     l2shuffled = [d , b]

Теперь попытайтесь ответить на два вопроса.

1. Какова вероятность того, что после объединения в окончательный результат a будет первым элементом списка.
Достаточно просто, мы можем видеть, что только две из четырех пар выше (опять же, равновероятных) могут дать такой результат (p1 = 1/2). Для каждой из этих пар heads должно быть нарисовано во время первого перелистывания в процедуре слияния (p2 = 1/2). Таким образом, вероятность наличия a в качестве первого элемента Lshuffled равна p = p1*p2 = 1/4, что верно.

2. Зная, что a находится на первой позиции Lshuffled, какова вероятность того, что c (мы могли бы также выбрать b или d без ограничения общности) на второй позиции Lshuffled
Теперь, согласно к приведенному выше определению идеально перетасованного списка ответ должен быть 1/3, так как есть три числа, которые нужно поместить в три оставшиеся ячейки в списке
Давайте посмотрим, гарантирует ли это алгоритм.
После выбора 1 в качестве первого элемента Lshuffled у нас будет либо:
l1shuffled = [c] l2shuffled = [b, d]
или:
l1shuffled = [c] l2shuffled = [d, b]
Вероятность выбора 3 в обоих случаях равна вероятности переворачивания heads (p3 = 1/2), таким образом, вероятность наличия 3 в качестве второго элемента Lshuffled, если известно, что первым элементом элемента Lshuffled является 1, равна 1/2. 1/2 != 1/3, что завершает доказательство неверности алгоритма.

Интересно то, что алгоритм выполняет необходимое (но недостаточное) условие идеального перемешивания, а именно:

Для списка из n элементов для каждого индекса k (<n) для каждого элемента ak: после перетасовки списка m раз, если мы подсчитали количество раз, когда ak встречалось в индексе k, это количество будет стремиться к m/n по вероятности, при этом m стремится к бесконечности.

На самом деле вы можете добиться большего: лучший алгоритм перетасовки списка — это O(n log n) времени и всего лишь O(1) пробела. (Вы также можете перетасовать O(n) времени и O(n) пространства, создав массив указателей для списка, перетасовав его на месте с помощью Кнута и повторно перетасовав список соответственно.)

Доказательство сложности

Чтобы понять, почему время O(n log n) минимально для пространства O(1), заметьте, что:

• С пространством O (1) обновление преемника произвольного элемента списка обязательно занимает время O (n).
• Wlog, вы можете предположить, что всякий раз, когда вы обновляете один элемент, вы также обновляете все остальные элементы (оставляя их без изменений, если хотите), так как это также занимает всего O (n) времени.
• С пространством O (1) можно выбрать не более O (1) элементов для преемника любого элемента, который вы обновляете (какие именно это элементы, очевидно, будет зависеть от алгоритма).
• Следовательно, одно обновление всех элементов за время O(n) может привести к не более чем c^n различным перестановкам списка.
• Так как есть n! = O(n^n) = O(c^(n log n)) возможных перестановок списка, вам требуется как минимум O(log n) обновлений.

Структура данных связанного списка (потому что Python)

import collections

class Cons(collections.Sequence):
    def __init__(self, head, tail=None):
        self.head = head
        self.tail = tail

    def __getitem__(self, index):
        current, n = self, index
        while n > 0:
            if isinstance(current, Cons):
                current, n = current.tail, n - 1
            else:
                raise ValueError("Out of bounds index [{0}]".format(index))
        return current

    def __len__(self):
        current, length = self, 0
        while isinstance(current, Cons):
            current, length = current.tail, length + 1
        return length

    def __repr__(self):
        current, rep = self, []
        while isinstance(current, Cons):
            rep.extend((str(current.head), "::"))
            current = current.tail
        rep.append(str(current))
        return "".join(rep)

Алгоритм слияния

Вот алгоритм времени O (n log n) и пространства O (1), основанный на итеративной сортировке слиянием. Основная идея проста: перетасовать левую половину, затем правую половину, а затем объединить их, выбрав случайным образом из двух списков. Стоит отметить две вещи:

1. Делая алгоритм итеративным, а не рекурсивным, и возвращая указатель на новый последний элемент в конце каждого шага слияния, мы уменьшаем потребность в пространстве до O (1), сохраняя при этом минимальные временные затраты.
2. Чтобы убедиться, что все возможности равновероятны для всех размеров входных данных, мы используем вероятности из модели перетасовки Гилберта-Шеннона-Ридса при слиянии (см. http://en.wikipedia.org/wiki/Gilbert%E2%80%93Shannon%E2%80%93Reeds_model).

import random

def riffle_lists(head, list1, len1, list2, len2):
    """Riffle shuffle two sublists in place. Returns the new last element."""
    for _ in range(len1 + len2):
        if random.random() < (len1 / (len1 + len2)):
            next, list1, len1 = list1, list1.tail, len1 - 1
        else:
            next, list2, len2 = list2, list2.tail, len2 - 1
        head.tail, head = next, next
    head.tail = list2
    return head

def shuffle_list(list):
    """Shuffle a list in place using an iterative merge-style algorithm."""
    dummy = Cons(None, list)
    i, n = 1, len(list)
    while (i < n):
        head, nleft = dummy, n
        while (nleft > i):
            head = riffle_lists(head, head[1], i, head[i + 1], min(i, nleft - i))
            nleft -= 2 * i
        i *= 2
    return dummy[1]

Другой алгоритм

Другой интересный алгоритм O(n log n), производящий не совсем однородные перетасовки, включает простое перетасовку списка 3/2 log_2(n) раз. Как описано в http://en.wikipedia.org/wiki/Gilbert%E2%80%93Shannon%E2%80%93Reeds_model остается только постоянное количество битов информации.

Вот одно из возможных решений:

#include <stdlib.h>

typedef struct node_s {
   struct node_s * next;
   int data;
} node_s, *node_p;

void shuffle_helper( node_p first, node_p last ) {
   static const int half = RAND_MAX / 2;
   while( (first != last) && (first->next != last) ) {
      node_p firsts[2] = {0, 0};
      node_p *lasts[2] = {0, 0};
      int counts[2] = {0, 0}, lesser;
      while( first != last ) {
         int choice = (rand() <= half);
         node_p next = first->next;
         first->next = firsts[choice];
         if( !lasts[choice] ) lasts[choice] = &(first->next);
         ++counts[choice];
         first = next;
      }

      lesser = (counts[0] < counts[1]);

      if( !counts[lesser] ) {
         first = firsts[!lesser];
         *(lasts[!lesser]) = last;
         continue;
      }

      *(lasts[0]) = firsts[1];
      *(lasts[1]) = last;

      shuffle_helper( firsts[lesser], firsts[!lesser] );

      first = firsts[!lesser];
      last = *(lasts[!lesser]);
   }
}

void shuffle_list( node_p thelist ) { shuffle_helper( thelist, NULL ); }

По сути, это быстрая сортировка, но без поворота и со случайным разделением.

Внешний цикл while заменяет рекурсивный вызов.

Внутренний цикл while случайным образом перемещает каждый элемент в один из двух подсписков.

После внутреннего цикла while мы соединяем подсписки друг с другом.

Затем мы рекурсивно работаем с меньшим подсписком и зацикливаемся на большем.

Поскольку меньший подсписок никогда не может быть больше половины размера исходного списка, в худшем случае глубина рекурсии составляет логарифмическую базу два от числа элементов. Необходимый объем памяти в O(1) раз больше глубины рекурсии.

Среднее время выполнения и количество вызовов rand() составляют O(N log N).

Более точный анализ во время выполнения требует понимания фразы «почти наверняка».

Сортировка слиянием снизу вверх без сравнения. при слиянии не сравнивайте, просто меняйте местами элементы.

Вы можете перемещаться по списку, случайным образом генерируя 0 или 1 в каждом узле.

Если он равен 1, удалите узел и поместите его первым узлом в списке. Если это 0, ничего не делайте.

повторяйте это, пока не дойдете до конца списка.