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

Ответ 1

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

Алгоритм.

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 элементов в стеке во время рекурсии.

Точка с манекеном node заключается в понимании того, что вставка и удаление фиктивного элемента сохраняет равномерность распределения элементов.

Анализ. Почему распределение равномерно? После окончательного слияния вероятность 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 четное и что два списка равномерно перетасовываются. Это достигается добавлением (а затем удалением) фиктивного node.

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

P.P.S. Есть ли способ вставить LaTeX здесь?

Ответ 2

код

Подход к тасованию

Эта (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] против отношения узлов, выведенных из первого списка, по общему количеству node (в двух списках).

Вниз пошаговый подход

Вы также можете перетасовать, когда вы подразделяете рекурсивно, что в моих скромных тестах показало немного (но последовательно) лучшую производительность. Это может быть связано с меньшим количеством инструкций или, с другой стороны, могло возникнуть из-за перегрева кеша в 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

Испытания

Полный источник находится в моем спискеShuffle.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

Ответ 3

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

Определение: предположим, что у нас есть List 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]. После перетасовки этих двух подписок (но до слияния с результатом из четырех элементов) мы можем получить четыре одинаково вероятных списка из 2 элементов:

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 стремится к бесконечности.

Ответ 4

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

Сложность

Чтобы понять, почему время 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) пространства, основанный на сортировке итеративного слияния. Основная идея проста: перетасуйте левую половину, затем правую половину, затем объедините их, случайно выбрав из этих двух списков. Следует отметить две вещи:

• Сделав алгоритм итеративным, а не рекурсивным, и возвращая указатель на новый последний элемент в конце каждого шага слияния, мы уменьшаем потребность в пространстве до O (1), сохраняя минимальные затраты времени.
• Чтобы убедиться, что все возможности одинаково вероятны для всех входных размеров, мы используем вероятности из перетасовки модели Gilbert-Shannon-Reeds при слиянии (см. 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, это оставляет только постоянное количество бит информации.

Ответ 5

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

Ответ 6

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

#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).

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