算法中的n log n次洗牌链表(Algorithm for Shuffling a Linked

我试图重新洗牌使用分而治之算法，随机打乱的linearithmic链表链表（N log n）的时间和对数（log n）的额外空间。

我知道，我可以做一个克努特洗牌类似，可以在值的简单阵列中使用，但我不知道我会如何与分而治之的做到这一点。 我的意思是，我在实际分割？ 难道我只是划分到列表中的每个单独的节点，然后使用一些随机值随机装配清单一起回来？

还是我给每个节点的随机数，然后执行节点上一个合并基础上的随机数？

Answer 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

空间的关键点是，拆分列表为两个不需要任何额外的空间。 我们唯一需要的额外的空间是保持递归中的堆栈上的日志n个元素。

与伪节点的一点是要意识到，插入和去除伪元件保持元件均匀的分布。

分析。 为什么是分布均匀？ 最终合并后，将概率P_i(n)中的位置结束了任何给定数目的i如下。 无论它是：

• 在i个发生在自己的列表，列表中赢得了抛硬币的第一个i的时间，这个概率是1/2^i ;
• 在i-1在自己的名单-st的地方，而列表赢得掷硬币i-1次，包括最后一个 ，失去了一次，这个概率是(i-1) choose 1次1/2^i ;
• 在i-2在其自己的名单-nd的地方，而列表赢得掷硬币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均匀，而且这两个名单均匀洗牌。 这是通过加入（然后除去）的虚节点来实现的。

PS我原来的直觉是隔靴搔痒严格，但我列出来，以防万一。 试想一下，我们随机1到n之间的数字分配到列表中的元素。 现在我们运行相对于这些数字的合并排序。 在合并的任何一步，它需要决定这两个列表的头较小。 但是，一个比另一个更大的概率应该是完全的1/2，因此我们可以通过抛硬币模拟此。

PPS有没有办法在这里嵌入LaTeX的？

Answer 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]均匀随机数完成弹出（在两个列表）。

唐氏洗牌方法

您也可以随机播放，而你递归细分，这在我卑微的测试结果显示略（但始终）更好的性能。 它可能来自更少的指令，或在另一方面，它可能会出现由于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要点 。

它包含的代码，在执行时，打印表示矩阵，对于输入列表中的每个元素，它出现的次数在输出列表中的每个位置，运行的指定次数后。 相当均匀的基质“显示”字符的分布的均匀性，所述洗牌因此均匀性。

下面是一个例子运行与使用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

Answer 3:

我说，那foxcub的答案是错误的。 为了证明我将介绍一个完全打乱列表一个有用的定义（称之为数组或序列或任何你想要的）。

定义：假设我们有一个列表L含有的元素a1, a2 ... an和指标1, 2, 3..... n 。 如果我们暴露L到的混洗操作（到内部构件我们没有访问） L当且仅当通过知道一些k的索引（是完全混洗k< n个元素，我们不能推断剩余的索引nk元素。 即剩余的nk元件是同样可能在任何剩余的被揭示nk索引。

例如：如果我们有一个四个元素列表[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必须在合并例程首先翻转（期间drawed 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 ， 则结束该算法的不正确的证明。

有趣的是，该算法fullfils必要（但不充分）条件，一个完美的洗牌，即：

给定的列表n元件，对于每个索引k （ <n对于每一个元件ak ：洗牌列表之后m倍，如果我们已经计数的次数时ak的发生k指数，此计数将趋向于m/n通过概率，与m趋于无穷大。

Answer 4:

实际上，你可以做的比这更好的：最好的名单洗牌算法是O（n log n）的时间 ，只是O（1）空间 。 （还可以通过构造一个指针数组为列表，使用Knuth的并重新穿线相应列表代替洗牌它洗牌在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日志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 ，这仅留下的信息位的常数。

Answer 5:

这里是一个可能的解决方案：

#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循环，我们的子列表彼此连接。

然后，我们调用那些更小的子表，并在更大的循环。

因为较小的子列表绝不可能的初始列表的超过一半的大小，递归的最坏的情况下深度为元件的数目的对数基2。 的所需的内存量是O（1）倍的递归深度。

的平均运行时间，和调用的数rand()为O（N日志N）。

更精确的运行时分析需要短语的理解“几乎肯定”。

Answer 6:

自下而上归并排序，而不进行比较。 而合并没有做任何比较，只是交换的元素。

文章来源: Algorithm for Shuffling a Linked List in n log n time